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