解题思路

本题是一棵带边权的树，有 $N$ 个节点，每个节点有收益 $g_i$ ，炸弹影响范围为 $K$ 。

如果炸弹放在节点 $x$ ，那么所有到 $x$ 的路径距离不超过 $K$ 的节点都会被摧毁，收益为这些节点收益之和。

由于树上任意两个节点之间路径唯一，可以枚举每个节点作为炸弹放置点，然后从该节点开始做一次 $DFS$ ，统计距离不超过 $K$ 的所有节点收益。

核心步骤：

题目内容

小明正在游玩一款爆破游戏。游戏地图可以抽象为一棵带权树，树上的节点从 0 开始编号。每个节点都有一个收益值，表示该节点被爆破后能够获得的收益；每条树边都有一个距离。

小明手中有一枚炸弹，可以任意选择一个节点放置。炸弹携带一个影响范围参数 $K$ 。如果某个节点到炸弹所在节点的树上路径长度不超过 $K$ ，那么这个节点就会被爆破。路径长度定义为路径上所有边的距离之和。

被爆破节点的收益会全部累加。请你帮助小明确定炸弹放置节点，使得累计收益最大，并输出这个最大值。

约束条件

选择提交后点击「开始AI分析」