Welcome to ZOJ
78 - ZOJ Monthly, May 2009 - I
Tree of Tree

Time Limit: 1 Second      Memory Limit: 32768 KB

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
A tree is a connected graph which contains no cycles.


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.

Sample Input

3 1
10 20 30
0 1
0 2
3 2
10 20 30
0 1
0 2

Sample Output


Author: LIU, Yaoting
Source: ZOJ Monthly, May 2009
Submit    Status