
78  ZOJ Monthly, May 2009  I
You're given a tree with weights of each node, you need to find the maximum subtree of specified size of this tree.
Tree Definition Input There are several test cases in the input. The first line of each case are two integers N(1 <= N <= 100), K(1 <= K <= N), where N is the number of nodes of this tree, and K is the subtree's size, followed by a line with N nonnegative integers, where the kth integer indicates the weight of kth node. The following N  1 lines describe the tree, each line are two integers which means there is an edge between these two nodes. All indices above are zerobase and it is guaranteed that the description of the tree is correct. Output One line with a single integer for each case, which is the total weights of the maximum subtree. Sample Input 3 1 10 20 30 0 1 0 2 3 2 10 20 30 0 1 0 2 Sample Output 30 40 Author: LIU, Yaoting Source: ZOJ Monthly, May 2009 