最优子树问题

Time Limit: 1000ms

Memory Limit: 65536k

Description


有一棵树,节点数为n(1<=n<=100 ),节点编号为(0,1,...,n-1)这棵树的每个点都有一个权值,现在要求你找出节点数为k( 1<=k<=n)的一个子树,并使这个子树的权值和最大。



Input

有若干组测试数据,第一行输入两个整数n,k

第二行输入n个整数,表示从0到n-1各个点的权值

接下来n-1行,输入两个点u,v,表示这两个点有一条边相连


Output

输出节点数大小为k的子树最大的权值和。

Sample Input

5 3
5 4 3 6 2
0 1
0 2
0 3
1 4

Sample Output

15

Hint

答案不会超过int

Source

shiwei

提交代码