CF990G GCD Counting

给定一棵包含 $n$ 个顶点的树。每个顶点上写有一个数字，第 $i$ 个顶点上的数字为 $a_i$。 我们定义函数 $g(x, y)$ 为从顶点 $x$ 到顶点 $y$ 的简单路径上所有顶点所写数字的最大公约数（包括 $x$ 和 $y$ 这两个顶点）。 对于每个从 $1$ 到 $2 \cdot 10^5$ 的整数，你需要统计有多少对 $(x, y)$ 满足 $1 \le x \le y \le n$ 且 $g(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$ 的边。保证这些边构成一棵树。

对于每个从 $1$ 到 $2 \cdot 10^5$ 的整数 $i$，如果不存在满足 $x \le y$ 且 $g(x, y) = i$ 的对 $(x, y)$，则不输出任何内容。否则，输出两个整数：$i$ 和满足条件的对数。输出时，$i$ 必须按升序排列。 具体格式可参考样例。

由 ChatGPT 4.1 翻译