GCD Counting

题意翻译

题意简述 给出一棵树，树有点权，求树上的一条链满足：链上所有点的点权的$gcd>1$且链上的点数最多．注意一个点也可以构成一条链． 输入数据 第一行一个正整数$n(1 \leq n \leq 2 \times 10^5)$表示树的点数 接下来一行$n$个正整数$a_i(1 \leq a_i \leq 2 \times 10^5)$表示每个点的点权 接下来$n-1$行每行两个正整数$u,v(1 \leq u,v \leq n , u \neq v)$表示树上的一条边． 输出数据 输出一行一个整数，如果不存在这样的链输出```0```，否则输出最长的可能链长．

题目描述

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.

输入输出样例

输入样例 #1

3
2 3 4
1 2
2 3

输出样例 #1

1

输入样例 #2

3
2 3 4
1 3
2 3

输出样例 #2

2

输入样例 #3

3
1 1 1
1 2
2 3

输出样例 #3

0

题意翻译

题意简述 给出一棵树，树有点权，求树上的一条链满足：链上所有点的点权的$gcd>1$且链上的点数最多．注意一个点也可以构成一条链． 输入数据 第一行一个正整数$n(1 \leq n \leq 2 \times 10^5)$表示树的点数 接下来一行$n$个正整数$a_i(1 \leq a_i \leq 2 \times 10^5)$表示每个点的点权 接下来$n-1$行每行两个正整数$u,v(1 \leq u,v \leq n , u \neq v)$表示树上的一条边． 输出数据 输出一行一个整数，如果不存在这样的链输出```0```，否则输出最长的可能链长．