说明

一组正整数 $S$ 的最大公约数（GCD）定义为最大的正整数 $d$，使得 $d$ 是 $S$ 中所有元素的约数，例如，$\text{GCD}(10) = 10$，$\text{GCD}(6, 9) = 3$，$\text{GCD}(20, 12, 16, 36) = 4$。

本题中，给定一棵具有 $N$ 个节点的树，节点编号从 $1$ 到 $N$，每个节点被赋予一个正整数 $A_i$。你的任务是找出最大的子树，使得该子树中所有节点权值的最大公约数不为 $1$，如果不存在这样的子树，则输出 $0$。树 $T'$ 是 $T$ 的子树当且仅当 $T'$ 是连通的且是 $T$ 的子集。子树的大小是指该子树中的节点数量。

例如，考虑下面一棵 $N = 7$ 个节点的树，其中 $A_{1..7} = \{10, 5, 8, 6, 10, 6, 4\}$。

:::align{center} :::

在这个例子中，有 $15$ 个子树，其所有节点权值的最大公约数不为 $1$，即七个大小为 $1$ 的子树，四个大小为 $2$ 的子树，三个大小为 $3$ 的子树，以及一个大小为 $4$ 的子树（最大的）。最大的子树包含节点 $4$、$5$、$6$ 和 $7$，它们权值的最大公约数为 $\text{GCD}(A_4, A_5, A_6, A_7) = \text{GCD}(6, 10, 6, 4) = 2$。

输入格式

输入第一行包含一个整数 $N$（$2 \leq N \leq 100\,000$），表示给定树的节点数量。下一行包含 $N$ 个整数 $A_i$（$1 \leq A_i \leq 10^6$），表示第 $i$ 个节点的权值。接下来 $N-1$ 行，每行包含两个整数 $u_j$ 和 $v_j$（$1 \leq u_j < v_j \leq N$），表示连接节点 $u_j$ 和 $v_j$ 的一条边。保证给定的树是连通的。

输出格式

输出一行一个整数，表示最大的子树的大小，该子树中所有节点权值的最大公约数不为 $1$。如果不存在这样的子树，则输出一行 $0$。

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

提示

样例 #2 解释

在这种情况下，不存在所有节点权值的最大公约数不为 $1$ 的子树。

翻译由 DeepSeek 完成