Divide Tree

Time Limit:1000MS  Memory Limit:65535KB
Description:
As we all know that we can consider a tree as a graph. Now give you a tree with nodes having its weight. We define the weight of a tree is the sum of the weight of all nodes on it. You know we can divide the tree into two subtrees by any edge of the tree. And your task is to tell me the minimum difference between the two subtrees’ weight.
Input:
   The first line, an integer T (T <= 30), representing T test cases blew.
   For each test case, the first line contains one integer N (2 <= N <= 10000), indicating the number of tree’s nodes.   
   Then follow N integers in one line, indicating the weight of nodes from 1 to N.
For next N-1 lines, each line contains two integers Vi and Vj (1 <= Vi, Vj <= N), indicating one edge of the tree.
 
Output:
For each test case, output the minimum weight difference. We assume that the result will not exceed 220.
Sample test:
Input
1
5
6 3 9 3 1
2 3
3 1
4 1
1 5
Output
2
Note:
Source:
Author:
ACSolo