题目描述

给定一棵包含 $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$，表示顶点数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ，表示每个顶点上的数字。

接下来 $n-1$ 行，每行包含两个整数 $x$ 和 $y$ ，表示一条连接顶点 $x$ 和顶点 $y$ 的边。保证这些边构成一棵树。

输出格式

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

3
2 3 4
1 2
2 3

1

3
2 3 4
1 3
2 3

2

3
1 1 1
1 2
2 3

0

说明 / 提示

由 ChatGPT 4.1 翻译

数据范围

$(1 \le n \le 2 \cdot 10^5)$

$(1 \le a_i \le 2 \cdot 10^5)$

$(1 \le x, y \le n, x \ne y)$