Emma has a tree of n nodes, each node has a value, now she wants to know the biggest sum of a path from the root to a leaf node.
Emma has a tree of n nodes, each node has a value, now she wants to know the biggest sum of a path from the root to a leaf node.
The first line will be an integer T, which is the number of test cases. (1 <= T <= 10). For each test case, the first line will be an integer n(1 <= n <= 105), n is the number of nodes. The second line will be n integer, a1……an(1 <= ai <= 109), ai is the value of the i-th node. Then followed by n - 1 lines, each line will be two integers x and y, it means x is the father of y, we promise that these node are numbered from 1 to n and the input is a tree.
For each test output the biggest sum.
1
3
1 2 3
1 2
1 34