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.
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 k-th integer indicates the weight of k-th 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 zero-base and it is guaranteed that the description of the tree is correct.
One line with a single integer for each case, which is the total weights of the maximum subtree.
3 1 10 20 30 0 1 0 2 3 2 10 20 30 0 1 0 2
Author: LIU, Yaoting
Source: ZOJ Monthly, May 2009