CF990G 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). For every integer from $ 1 $ to $ 2 \cdot 10^5 $ you have to count the number of pairs $ (x, y) $ $ (1 \le x \le y \le n) $ such that $ g(x, y) $ is equal to this number.

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.

For every integer $ i $ from $ 1 $ to $ 2 \cdot 10^5 $ do the following: if there is no pair $ (x, y) $ such that $ x \le y $ and $ g(x, y) = i $ , don't output anything. Otherwise output two integers: $ i $ and the number of aforementioned pairs. You have to consider the values of $ i $ in ascending order. See the examples for better understanding.