CF1101D.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). Also let's denote $dist(x, y)$ as the number of vertices on the simple path between vertices $x$ and $y$, including the endpoints. $dist(x, x) = 1$ for every vertex $x$.

Your task is calculate the maximum value of $dist(x, y)$ among such pairs of vertices that $g(x, y) \gt 1$.

给你一棵包含 $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)$ 的最大值。

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$ 的边。保证这些边构成一棵树。

If there is no pair of vertices $x, y$ such that $g(x, y) \gt 1$, print $0$. Otherwise print the maximum value of $dist(x, y)$ among such pairs.

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