[Login|Register]
Problems

Status

Rank

Problem 1232
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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.1ms with 1 query(s).