| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem C
Divide Tree
Time Limit: 1000ms
Memory Limit: 65536kb 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 2^20.
Sample Input
1 5 6 3 9 3 1 2 3 3 1 4 1 1 5 Sample Output
2 |