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

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

There is a rooted tree of N$N$ vertices rooted at vertex 1$1$. Each vertex v$v$ has a value Av$A_v$ associated with it.

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

The beauty of a connected component is the GCD$\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$v$.

Solution Click Below:-  CLICK HERE

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

Input Format

• The first line contains a single integer T$T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N$N$ — the size of the tree.
• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ denoting the values associated with each vertex.
• The next N−1$N-1$ lines contain two space-separated integers u$u$ and v$v$ — denoting an undirected edge between nodes u$u$ and v$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$v$.

Constraints

• 1≤T≤2⋅104$1\le T\le 2\cdot {10}^4$
• 1≤N≤3⋅105