考点：树

数据规模 n ≤ 100 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：n ≤ 100
• 元素值域：k ≤ 100000000，g_i ≤ 1e5，d ≤ 1e5（注意整数类型选择，避免溢出）
• 复杂度门槛：允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：树

本题切入点

n≤100 极小，直接枚举放置点：对每个候选点从它出发 DFS 累加树上距离 ≤k 的节点收益取最大（也可用换根 DP 降到 O(n)）。

树结构上的遍历（DFS 求子树信息 / BFS 求层序），多数树题是「后序遍历 + 回溯」。

思路框架（树 通法 · 非本题专属）

1. 按输入建图（父子关系一般给父节点编号，孩子用邻接表存）。
2. 确定遍历方式：自底向上合并子树信息（后序 DFS）或自顶向下传参（前序 DFS）。
3. 对每个节点，用孩子的答案合并出当前节点的答案。
4. 涉及层间操作（如层序变换）时用 BFS 逐层处理。

实现要点：递归深度可能到 1e5，注意递归爆栈；必要时改迭代或调整递归深度。

复杂度：时间 O(n) ｜ 空间 O(n)

该范式的通法易错点

• 递归深度过大导致爆栈。
• 建树时父子关系方向搞反（把树当成有向图但遍历方向错）。

对照本题

• 数据规模 n ≤ 100，允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
• 元素值域最大到 100000000 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 7 3 / 10 10 10 300 10 10 300 / 0 1 1 / 0 2 1 / 1 3 3 / 1 4 1 / 2 5 3 / 2 6 1 → 输出 640

选择合适节点后，半径范围内节点收益之和为 640。

样例 2：输入 5 2 / 200 100 250 100 100 / 1 0 20 / 0 2 20 / 3 1 2 / 4 1 2 → 输出 300

最优放置点可覆盖收益总和为 300 的节点集合。