光棱坦克题解¶

解法比较¶

出题人解法枚举最终开火的根，对树做动态规划：把孩子的贡献降序排列，枚举保留的孩子数 \(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\) .