1893. 采花

单点时限: 5.0 sec

内存限制: 256 MB

春天来了 ,ECNU 校园内很多花都开了,嗯,小强和一个 MM 逛校园,看到有棵树上的花开的很特别,所以 MM 要小强去采花给她,小强只有去采了,这棵树上有 n 个树枝,从 1 到 n 标记,每个树枝上有 X 朵花,小强所在的节点是 1,MM 有时间限制,小强经过 K 步后就不能采花了,马上要把花给她。这 n 个节点是个树形结构,要求小强经过 K 步后采得的花最多。小强从一个树枝到相邻的树枝需要 1 步。小强找到太阳 GG 我帮他计算下最多能采到多少花,偶只有找你们帮忙了。

输入格式

多 Case, 开始 n( <= 200 ),k ( <= 400 ),表示这棵树有 n 个树枝 (1…n),k 表示小强可以走 K 步。接下来一行有 n 个数,代表从 1 到 n 树枝上花朵的数目。
接下来 n-1 行,每行 2 个数 a b, 表示树枝 a 和 b 相邻。
小强开始在树枝 1.

输出格式

对每个 case, 输出小强最多能采到的花朵数量 .(结果不会超过 int)

样例

Input
2 1
999 292
1 2
3 2
385 345 797
1 3
1 2
Output
1291
1182

8 人解决,21 人已尝试。

11 份提交通过,共有 65 份提交。

7.7 EMB 奖励。

创建: 13 年,9 月前.

修改: 4 年,5 月前.

最后提交: 6 月,2 周前.

来源: N/A

题目标签