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 N-1 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 N-1 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 (1-indexed).
Each of the next N-1 lines contains two integer values, u and v representing two vertices that share an edge.
Output answer for each test case on a new line.
1 <= T <= 10
1 <= N <= 100000
-109 <= Scorei <= 109
1 <= u,v <= N
NOTE: Please use fast I/O (scanf/printf for C++)
5 -1 2 3 -4
|Tags||dynamic-programming, medium, nkcb2016, torque, torque, tree|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, PAS fpc, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.