Ilya And The Tree

题意翻译

题意: 有一个n个节点的数,每个点有一个点权,根到这个点的所有点权(包括这个点和根)的gcd值为这个点的答案. 对于每一个点的答案,你可以删除其到根节点的路径上的至多一个点来使答案最大. 求每个点的答案(最大值). PS:根为1号点. 输入数据: 第一行一个整数n. 第二行n个数,为n个数的点权. 接下来n-1行<x,y>,表示x与y有连边. 输出数据: 一行n个数,分别为每个点的答案的最大值. 数据范围: n,x:[1,2e5] 注意: 对于每一个点,删除的点可以不一样,且之前删除的点要还原. 感谢@尘染梦 提供的翻译

题目描述

Ilya is very fond of graphs, especially trees. During his last trip to the forest Ilya found a very interesting tree rooted at vertex $ 1 $ . There is an integer number written on each vertex of the tree; the number written on vertex $ i $ is equal to $ a_{i} $ . Ilya believes that the beauty of the vertex $ x $ is the greatest common divisor of all numbers written on the vertices on the path from the root to $ x $ , including this vertex itself. In addition, Ilya can change the number in one arbitrary vertex to $ 0 $ or leave all vertices unchanged. Now for each vertex Ilya wants to know the maximum possible beauty it can have. For each vertex the answer must be considered independently. The beauty of the root equals to number written on it.

输入输出格式

输入格式


First line contains one integer number $ n $ — the number of vertices in tree ( $ 1<=n<=2·10^{5} $ ). Next line contains $ n $ integer numbers $ a_{i} $ ( $ 1<=i<=n $ , $ 1<=a_{i}<=2·10^{5} $ ). Each of next $ n-1 $ lines contains two integer numbers $ x $ and $ y $ ( $ 1<=x,y<=n $ , $ x≠y $ ), which means that there is an edge $ (x,y) $ in the tree.

输出格式


Output $ n $ numbers separated by spaces, where $ i $ -th number equals to maximum possible beauty of vertex $ i $ .

输入输出样例

输入样例 #1

2
6 2
1 2

输出样例 #1

6 6 

输入样例 #2

3
6 2 3
1 2
1 3

输出样例 #2

6 6 6 

输入样例 #3

1
10

输出样例 #3

10