Time Limit: 3000 MS Memory Limit: 65536 K

## Description

456 has a tree of n nodes, each node is assigned with an
integer number. Now 456 wants to select a subtree, such that
the sum of all integers on the nodes of the subtree is maxmized.
Can you help him?
## Input

On the first line of the input is an integer T, and then T
cases follows. Each case begins with a positive integer n(1 <= n <= 10^5),
then n numbers Wi(-1000 <= Wi <= 1000),Wi for
the number on the ith node. Then n - 1 lines follows, each
line contains two numbers a, b(1 <= a, b <= n)
indicate that there is a edge between node a and b.
## Output

For each test case, output one integer on a line,
the maximized sum can be achieved by selecting a subtree.
## Sample Input

3
1
5
2
5 -5
1 2
5
-2 -3 7 -1 4
1 2
2 3
3 4
2 5
## Sample Output

5
5
8
## Author

456
## Source

Sichuan University Programming Contest 2011 Preliminary