题目描述

题目简述：树版[k取方格数]

众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略 $k$ 部游戏。

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

“为什么你还没玩就知道每个场景的价值呢？”
“我已经看到结局了。”

输入格式

第一行两个正整数 $n$，$k$。
第二行 $n$ 个正整数，表示每个场景的价值。
以下 $n - 1$ 行，每行 $2$个整数 $a$，$b$，表示 $a$ 场景有个选择支通向 $b$ 场景（即 $a$ 是 $b$ 的父亲）。

输出格式

输出一个整数表示答案

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

10

提示

对于 $100\%$ 的数据，$n \le 2 \times 10^5，1 \le \text{场景价值} \le 2^{31} - 1$。

保证场景 $1$ 为根节点。

题目来源

dfs 序 + 线段树