## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Full Path Eraser CodeChef Solution | CodeChef Problem Solution 2022

There is a rooted tree of $N$ vertices rooted at vertex $1$. Each vertex $v$ has a value ${A}_{v}$ associated with it.

You choose a vertex $v$ (possibly the root) from the tree and remove all vertices on the path from the root to the vertex $v$, also including $v$. This will result in a forest of zero or more connected components.

The beauty of a connected component is the $\mathrm{G}\mathrm{C}\mathrm{D}$ of the values of all vertices in the component. Find the maximum value of the sum of beauties of the obtained connected components for any choice of $v$.

Here, $\mathrm{G}\mathrm{C}\mathrm{D}$ stands for Greatest Common Divisor.

### Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ — the size of the tree.
• The second line of each test case contains $N$ space-separated integers ${A}_{1},{A}_{2},\dots ,{A}_{N}$ denoting

•  the values associated with each vertex.
• The next $N-1$ lines contain two space-separated integers $u$ and $v$ — denoting an undirected edge between nodes $u$ and $v$.

It is guaranteed that the edges given in the input form a tree.

### Output Format

For each test case output the maximum value of the sum of beauties of the obtained connected components for any choice of $v$.

### Constraints

• $1\le T\le 2\cdot {10}^{4}$
• $1\le N\le 3\cdot {10}^{5}$