D. GCD Counting
data structures; dfs and similar; dp; number theory; trees
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.