G. GCD Countingtime limit per test4.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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.OutputFor 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.ExamplesInput31 2 31 22 3Output1 42 13 1Input61 2 4 8 16 321 66 33 44 26 5Output1 62 54 68 116 232 1Input49 16 144 61 32 34 3Output1 12 13 16 29 216 2144 1
Input31 2 31 22 3
Output1 42 13 1
['divide and conquer', 'dp', 'dsu', 'number theory', 'trees', '*2400']