CF842C.Ilya And The Tree

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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 
```

首页