CF990G.GCD Counting

You are given a tree consisting of $n$ vertices. A number is written on each vertex; the number on vertex $i$ is equal to $a_i$.

Let's denote the function $g(x, y)$ as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex $x$ to vertex $y$ (including these two vertices).

For every integer from $1$ to $2 \cdot 10^5$ you have to count the number of pairs $(x, y)$ $(1 \le x \le y \le n)$ such that $g(x, y)$ is equal to this number.

给你一棵包含 $n$ 个顶点的树。每个顶点上写有一个数字；顶点 $i$ 上的数字为 $a_i$。

定义函数 $g(x, y)$ 为从顶点 $x$ 到顶点 $y$ 的简单路径（包含端点 $x$ 和 $y$）上所有顶点所写数字的最大公约数（GCD）。

对于从 $1$ 到 $2 \cdot 10^5$ 的每一个整数，你需要统计满足 $g(x, y)$ 等于该整数的顶点对 $(x, y)$（其中 $1 \le x \le y \le n$）的个数。

The first line contains one integer $n$ — the number of vertices $(1 \le n \le 2 \cdot 10^5)$.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ $(1 \le a_i \le 2 \cdot 10^5)$ — the numbers written on vertices.

Then $n - 1$ lines follow, each containing two integers $x$ and $y$ $(1 \le x, y \le n, x \ne y)$ denoting an edge connecting vertex $x$ with vertex $y$. It is guaranteed that these edges form a tree.

第一行包含一个整数 $n$ —— 顶点的数量（$1 \le n \le 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $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$ 的边。保证这些边构成一棵树。

For every integer $i$ from $1$ to $2 \cdot 10^5$ do the following: if there is no pair $(x, y)$ such that $x \le y$ and $g(x, y) = i$, don't output anything. Otherwise output two integers: $i$ and the number of aforementioned pairs. You have to consider the values of $i$ in ascending order.

See the examples for better understanding.

对每个从 $1$ 到 $2 \cdot 10^5$ 的整数 $i$，执行以下操作：若不存在满足 $x \le y$ 且 $g(x, y) = i$ 的数对 $(x, y)$，则不输出任何内容；否则输出两个整数：$i$ 和满足上述条件的数对个数。你需要按 $i$ 的升序依次处理这些值。

参见示例以获得更清晰的理解。