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) > 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.