题目描述

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., $\text{GCD}(10) = 10$, $\text{GCD}(6, 9) = 3$, $\text{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 $A_i$ 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\}$.

:::align{center} :::

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 $\text{GCD}(A_4, A_5, A_6, A_7) = \text{GCD}(6, 10, 6, 4) = 2$.

输入格式

Input begins with a line containing an integer $N$ ($2 \leq N \leq 100\,000$) representing the number of nodes in the given tree. The next line contains $N$ integers $A_i$ ($1 \leq A_i \leq 10^6$) representing the weight of the $i^{th}$ node. The next $N - 1$ line each contains two integers $u_j$ $v_j$ ($1 \leq u_j < v_j \leq 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.

7
10 5 8 6 10 6 4
1 2
2 3
2 4
4 5
4 6
4 7

4

4
1 1 1 1
1 2
2 3
3 4

0

5
100 100 100 100 100
3 4
1 2
3 5
2 4

5

提示

Explanation for the sample input/output #2

There is no subtree where the GCD of all its nodes' weight is not $1$ in this case.