10651065 SUSTech Online Judge
Problem 1065 --Find the most valuable path

1065: Find the most valuable path

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 1125  Solved: 173
[Submit][Status][Web Board]

Description

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.

Input

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.

Output

For each test output the biggest sum.

Sample Input

1
3
1 2 3
1 2
1 3

Sample Output

4

HINT

Source

 

[Submit][Status]