26855번 - Not One 다국어

The greatest common divisor (GCD) of a set of positive integers S is defined as the largest positive integer d such that d is a divisor for all elements in S, e.g., GCD(10) = 10, GCD(6, 9) = 3, GCD(20, 12, 16, 36) = 4.

In this problem, you are given a tree of N nodes where each node is numbered from 1 to N and has a positive integer Ai assigned to it. Your task is to find the size of the largest subtree such that the GCD of the weight of all nodes in that subtree is not 1, or output 0 if there is no such a subtree. A tree T' is a subtree of T if and only if T' is connected and is a subset of T. The size of a subtree is the number of nodes in that subtree.

For example, consider the following tree of N = 7 nodes where A_1..7 = {10, 5, 8, 6, 10, 6, 4}.

In this example, there are 15 subtrees where the GCD of all its nodes’ weight is not 1, i.e. seven subtrees of size 1, four subtrees of size 2, three subtrees of size 3, and one subtree of size 4 (the largest). The largest subtree contains nodes 4, 5, 6, and 7, and the GCD of their weights is GCD(A₄, A₅, A₆, A₇) = GCD(6, 10, 6, 4) = 2.

Input begins with a line containing an integer N (2 ≤ N ≤ 100 000) representing the number of nodes in the given tree. The next line contains N integers A_i (1 ≤ A_i ≤ 10⁶) representing the weight of the i^th node. The next N − 1 line each contains two integers u_j v_j (1 ≤ u_j < v_j ≤ N) representing an edge connecting node u_j and node v_j. It is guaranteed that the given tree is connected.

Output contains an integer in a line representing the size of the largest subtree such that the GCD of all its nodes’ weight is not 1. If there is no such a subtree, output 0 in a line.