T602946 【2025 年 5 月月赛赛题 D】树上安全距离

[Hydro 域链接](https://hydro.ac/d/chenyuan3_s_online_judge/p/Contest202505D)。 本题由 DeepSeek 生成，并由 @[chenyuan3](/user/559528) 完善。[题解](https://chenyuan33a.freeflarum.com/d/176)

给定一棵包含 $n$ 个节点的树，每个节点有一个权值 $a_i$。请选出若干节点，使得任意两个被选节点的距离至少为 $k$。求被选节点的最大权值和。

第一行两个整数 $n$, $k$。 第二行 $n$ 个整数，表示每个节点的权值 $a_1$ 到 $a_n$。 接下来 $n-1$ 行，每行两个整数 $u$, $v$，表示一条边。

输出一个整数，表示最大权值和。

**【样例解释】** 选择节点 $3$、$4$、$5$，权值和为 $30+40+50=120$。节点间距离均 $\ge2$。 **【数据范围】** 对于 $10\%$ 的数据，满足 $n\le10$，$k\le3$； 对于 $100\%$ 的数据，满足 $k\le n\le10^5$，$1\le k\le10^3$。