← 返回题目列表

Codeforces · 1101/D

D. GCD 计数

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 个顶点组成的树。每个顶点上都写有一个数字;顶点 $$$i$$$ 上的数字等于 $$$a_i$$$。

让我们将函数 $$$g(x, y)$$$ 表示为属于从顶点 $$$x$$$ 到顶点 $$$y$$$(包括这两个顶点)的简单路径的顶点上所写的数字的最大公约数。另外,我们将 $$$dist(x, y)$$$ 表示为顶点 $$$x$$$ 和 $$$y$$$ 之间的简单路径上的顶点数,包括端点。对于每个顶点 $$$x$$$,$$$dist(x, x) = 1$$$。

你的任务是计算 $$$g(x, y) > 1$$$ 的顶点对中 $$$dist(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$$$ 的边。保证这些边形成一棵树。

输出

如果没有一对顶点 $$$x, y$$$ 使得 $$$g(x, y) > 1$$$,则打印 $$$0$$$。否则打印这些对中 $$$dist(x, y)$$$ 的最大值。

示例

输入 #1

3
2 3 4
1 2
2 3

输出 #1

1

输入 #2

3
2 3 4
1 3
2 3

输出 #2

2

输入 #3

3
1 1 1
1 2
2 3

输出 #3

0