Preparando MOJI
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) > 1$$$.
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.
If there is no pair of vertices $$$x, y$$$ such that $$$g(x, y) > 1$$$, print $$$0$$$. Otherwise print the maximum value of $$$dist(x, y)$$$ among such pairs.
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
Informação
Provedor Codeforces
Código CF1101D
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 09:43:57
Relacionados