Torque and edges

All submissions for this problem are available.
Torque and Egdes
Torque (Yes! we don't have Chef today :P), the scientist is performing weird experiment on a tree. His tree contains N vertices and N1 edges. Each vertex has some integer score associated with it. During his experiment, Torque can delete any edge from tree. This results in two connected components. Now, he will discard one component and keep the other component with him. He may perform his experiment any number of times (possibly none, at most N1 times).
In the end total score is the sum of scores of all nodes present in the tree left with Torque. Your task is to tell the maximum possible score.
The first line contains a single integer T representing number of test cases.
The first line of each test case contains a single integer N representing the number of vertices in the tree.
The second line contains N values representing the scores of each individual vertex (1indexed).
Each of the next N1 lines contains two integer values, u and v representing two vertices that share an edge.
Output
Output answer for each test case on a new line.
Constraints
1 <= T <= 10
1 <= N <= 100000
10^{9} <= Score_{i} <= 10^{9}
1 <= u,v <= N
NOTE: Please use fast I/O (scanf/printf for C++)
Sample Input:
1
5
5 1 2 3 4
1 2
3 1
4 5
1 4
Sample Output:
10
Author:  torque 
Editorial  https://discuss.codechef.com/problems/TRANDED 
Tags  dynamicprogramming, medium, nkcb2016, torque, torque, tree 
Date Added:  20092016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, PAS fpc, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 