给你一棵由 $$$n$$$ 个顶点组成的树。每个顶点上都写有一个数字;顶点 $$$i$$$ 上的数字等于 $$$a_i$$$。
让我们将函数 $$$g(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$$$, ..., $$$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, y)$$$ 使得 $$$x \le y$$$ 且 $$$g(x, y) = i$$$,则不输出任何内容。否则输出两个整数:$$$i$$$ 和上述对的数量。您必须按升序考虑 $$$i$$$ 的值。
请参阅示例以更好地理解。
示例
输入 #1
3 1 2 3 1 2 2 3
输出 #1
1 4 2 1 3 1
输入 #2
6 1 2 4 8 16 32 1 6 6 3 3 4 4 2 6 5
输出 #2
1 6 2 5 4 6 8 1 16 2 32 1
输入 #3
4 9 16 144 6 1 3 2 3 4 3
输出 #3
1 1 2 1 3 1 6 2 9 2 16 2 144 1