Problems Status Rank Problem 1232 Divide Tree Time Limit: 1000msMemory 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.2ms with 1 query(s).