BZOJ3252 攻略

众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略 $k$ 部游戏。 今天他得到了一款新游戏《XX 半岛》，这款游戏有 $n$ 个场景，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同时攻略 $k$ 次该游戏，问他观赏到的场景的价值和最大是多少？（同一场景观看多次是不能重复得到价值的） >“为什么你还没玩就知道每个场景的价值呢？” >“我已经看到结局了。”

给定一个有 $n$ 个结点的树，树有点权且点权为正整数。现选取 $k$ 条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。

第一行两个正整数 $n,k$。 第二行输入 $n$ 个正整数 $w_i$，表示每个结点的点权。 第三行输入 $n-1$ 行，每行 $2$ 个正整数 $u,v$，表示结点 $u$ 是结点 $v$ 的父亲。

输出一个正整数，表示答案。

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

10

对于所有数据，保证 $1\leq n\leq 2\times 10^5$，$1\leq w_i\leq 2^{31}-1$。