Migrated from Lutece 391 The Weight of Tree

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

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\leq n\leq 10^5$), then $n$ numbers $W_i$($-1000\leq W_i\leq 1000$),$W_i$ for the number on the $i_{th}$ node. Then $n - 1$ lines follows, each line contains two numbers $a$, $b$($1\leq a, b\leq 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.

Samples

3
1
5
2
5 -5
1 2
5
-2 -3 7 -1 4
1 2
2 3
3 4
2 5

5
5
8

Resources

10th SCU Programming Contest Final