CF842C.Ilya And The Tree

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.

伊利亚非常喜欢图，尤其是树。在他最近一次森林之旅中，伊lya发现了一棵非常有趣的、以顶点 1 为根的树。树的每个顶点上都写有一个整数；顶点 $i$ 上写的数为 $a_i$。

伊利亚认为，顶点 $x$ 的“优美值”（beauty）等于从根到 $x$ 的路径上（包含 $x$ 本身）所有顶点所写数字的最大公约数（GCD）。此外，伊利亚可以将至多一个任意顶点上的数改为 0，或者选择不作任何修改。现在，对于每个顶点，伊利亚想知道它所能达到的最大可能的优美值。

对每个顶点，答案需独立考虑（即每次仅针对一个顶点优化，可重新选择是否将某一个顶点设为 0）。

根节点的优美值即为其自身所写的数字。

First line contains one integer number n — the number of vertices in tree (1 ≤ n ≤ 2·105).

Next line contains n integer numbers a__i (1 ≤ i ≤ n, 1 ≤ a__i ≤ 2·105).

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.

第一行包含一个整数 $ n $ —— 树中顶点的数量（$ 1 \leq n \leq 2 \cdot 10^5 $）。

第二行包含 $ n $ 个整数 $ a_i $（$ 1 \leq i \leq n $，$ 1 \leq a_i \leq 2 \cdot 10^5 $）。

接下来的 $ n-1 $ 行中，每行包含两个整数 $ x $ 和 $ y $（$ 1 \leq x, y \leq n $，$ x \neq y $），表示树中存在一条边 $ (x, y) $。

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

输出 n 个用空格分隔的数字，其中第 i 个数字等于顶点 i 的最大可能美观度。