Tree#4248
Dear contestant, I bet you must know what a tree represents. In data structures, we learn that a tree is a graph in which every two nodes have one and only one path between them. Here comes an easy problem: given a tree with nodes that have weights, the weight of a tree is the sum of the weights of all its nodes. Now we have a chance to divide the tree into two subtrees, and we want to know the minimum difference between the weights of the two subtrees.
The first line contains a single integer , indicating the number of test cases. Each test case begins with one integer (2 \leq N \leq 10000), indicating the number of nodes in the tree. Then integers W_i (1 \leq W_i \leq 1000) follow, indicating the weights of the nodes from to .
Then N - 1 lines follow, each line contains two integers A_i and B_i (1 \leq A_i, B_i \leq N), indicating one edge of the tree.
For each test case, output one integer, indicating the minimum weight difference.
Example 1