#P3252. 攻略

攻略

攻略

题目描述

桂木桂马得到了一款游戏《XX 半岛》。游戏的 nn 个场景由剧情选项连成一棵有根树。每次从根场景开始,沿剧情选项一直走到某个叶子场景,即一个结局。

桂马同时攻略 kk 次,每次可以自行选择路线。每个场景有一个价值,多次经过同一个场景只计一次价值。求能获得的总价值的最大值。

“为什么你还没玩就知道每个场景的价值呢?”

“我已经看到结局了。”

输入格式

第一行包含两个正整数 n,kn,k。第二行包含 nn 个正整数,按编号给出各场景的价值。

接下来 n−1n-1 行,每行两个整数 a,ba,b,表示从场景 aa 有一个剧情选项通向场景 bb。场景 11 是根。

输出格式

输出一个整数,表示能获得的最大总价值。

样例

5 2
4 3 2 1 1
1 2
1 5
2 3
2 4
10

数据规模与约定

n≤200000n\le200000,每个场景的价值在 [1,231−1][1,2^{31}-1] 内。

BZOJ 归档题面