# 光棱坦克题解

## 解法比较

出题人解法枚举最终开火的根，对树做动态规划：把孩子的贡献降序排列，枚举保留的孩子数 $k$ ，用前 $k$ 项之和乘相应衰减系数，再加当前点伤害。固定 $k$ 时显然应选贡献最大的孩子；从叶子归纳即可得到下文的递推。不能屏蔽时保留全部孩子。

Codex（GPT-6）的实现生成显式遍历顺序，再逆序计算，避免深树递归。最坏时间为 $O(n^2\log(n+1))$ ，空间为 $O(n)$ .系数、取整与边界处理见下文。

## 阻断能力只需区分两种情况

$b=0$ 时不能阻断任何边。$b\ge1$ 时，任意边集都可以被阻断：给森林每个连通分量任选一个根，让每条待阻断边的子节点选择这条父边。每个顶点只有一条父边，因此至多选择一条边，符合名额限制。即使同一顶点周围有很多条边需要阻断，也可以把选择这些边的任务交给相应的孩子。

## 枚举攻击点

固定初始攻击点为根，只访问它所在的连通分量。树上路径唯一：当非根顶点 $u$ 被击中时，它的父节点已经被击中，孩子尚未被击中。因此，下一步只会沿未阻断的边进入孩子的子树。

设 $f_u$ 为已经击中 $u$ 时，通过预先选定其子树内的阻断方案所能获得的最大期望伤害，包含 $u$ 自身的伤害。若保留通向 $k\ge1$ 个孩子 $v_1,\ldots,v_k$ 的边，则它们的期望贡献为

$$\left(p_u+\frac{1-p_u}{k}\right)\sum_{j=1}^k f_{v_j}$$

这是因为每个孩子被击中的概率都是 $p_u+(1-p_u)/k$ ：全体折射时必然击中，单点折射时以 $1/k$ 的概率被选中。不同孩子的子树互不相交，可以预先为它们分别选择最优阻断方案。孩子之间是否被击中可能相关，但期望的线性性仍然允许我们直接相加。

当 $b=0$ 时必须保留通向全部孩子的边，直接代入它们的数量与 $f$ 值之和；没有孩子时，贡献为零。

当 $b\ge1$ 时，把所有孩子的 $f$ 值从大到小排序，枚举保留数量 $k$ ，用前缀和计算贡献。相同 $k$ 下系数相同且非负，因此选最大的 $k$ 项最优。也考虑不保留孩子，贡献为零。取这些方案的最大贡献，最后加上 $d_u$ .

自底向上计算根的答案，再枚举所有顶点作为根取最大值。程序使用迭代遍历，避免长链递归。

## 正确性

叶子的最优值是自身伤害。假设所有孩子的最优值均已正确计算。保留的孩子集合确定后，贡献公式中的系数非负，所以让每个孩子采用自己的最优子树方案最优。这些方案作用于不同子树，而且所需的删边集合在 $b\ge1$ 时一定可以实现。

若不能阻断，算法计算唯一允许的孩子集合；若可以阻断，算法枚举所有保留数量，并为每个数量选出最优集合。因此转移既不会漏掉最优方案，也不会使用无法实现的方案。加上自身伤害后得到 $f_u$ ，树形归纳便证明固定根的答案正确。最后枚举所有顶点作为根，覆盖了森林中的全部攻击点。

## 复杂度与精度

时间 $O(n^2\log n)$ ，空间 $O(n)$ ；孤立点也正常参与比较。使用浮点数计算期望，最后显式执行 $\lfloor V+\delta+0.5\rfloor$ ，不依赖格式化输出的舍入模式。题目保证距离半整数分界至少 $0.2$ .

代码中 `BlockLimit` 对应阻断名额 $b$ ，`RoundingOffset` 对应取整偏移量 $\delta$ .