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.

Submit: 1125 Solved: 173

[Submit][Status][Web Board]

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 <= 10^{5}), n is the number of nodes. The second line will be n integer, a_{1}……a_{n}(1 <= a_{i} <= 10^{9}), a_{i} 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 3
```

`4`