CF1101D GCD Counting

给定一棵包含 $n$ 个顶点的树，每个顶点上写有一个数字，第 $i$ 个顶点上的数字为 $a_i$。 我们定义函数 $g(x, y)$ 表示从顶点 $x$ 到顶点 $y$ 的简单路径上所有顶点所写数字的最大公约数（包括 $x$ 和 $y$）。同时，定义 $dist(x, y)$ 为从顶点 $x$ 到顶点 $y$ 的简单路径上顶点的数量（包括起点和终点）。对于任意顶点 $x$，有 $dist(x, x) = 1$。 你的任务是计算所有满足 $g(x, y) > 1$ 的顶点对 $(x, y)$ 中，$dist(x, y)$ 的最大值。

第一行包含一个整数 $n$，表示顶点数 $(1 \le n \le 2 \cdot 10^5)$。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 2 \cdot 10^5)$，表示每个顶点上的数字。 接下来 $n-1$ 行，每行包含两个整数 $x$ 和 $y$ $(1 \le x, y \le n, x \ne y)$，表示一条连接顶点 $x$ 和顶点 $y$ 的边。保证这些边构成一棵树。

如果不存在满足 $g(x, y) > 1$ 的顶点对 $(x, y)$，输出 $0$。否则，输出所有满足条件的顶点对中 $dist(x, y)$ 的最大值。

由 ChatGPT 4.1 翻译