# 砍树：题解

## 解法比较

标程采用静态最长链分解。它把收益提取阶段从动态子树修改的 $O(n\log(n+1))$ 降至 $O(n)$ ，并省去区间维护数组。最终排序使总时间仍为 $O(n\log(n+1))$ .

出题人解法在每棵树上按 DFS 序建线段树，初值为各点的根路径长度。反复选当前得分最高的端点，沿父链走到已经使用的部分；每新覆盖一个点，就把该点子树的所有端点得分减一。这样叶子得分始终是该根路径尚未覆盖的点数。每点只触发一次子树修改，便得到各次操作的边际收益。最后将各树收益合并排序；并列时优先已经启用的树，以减少启用树数。

Codex（GPT-6）采用的实现直接按最长孩子分解树，收集相同的边际收益，用“首项／非首项”标记表达并列规则，证明见下文。两者总时间均为 $O(n\log(n+1))$ 、空间为 $O(n)$ ，其中Codex 实现的对数来自排序。收益是免去区间减法结构和沿父链的动态扣减，并采用显式遍历；收益提取为线性时间，总时间中的对数来自最终排序。

## 一棵树的收益序列

选中内部节点不会比选中它的某个后代叶子更好，因此可以把预算理解为选择若干条通向叶子的根路径。砍完整棵树时，每个叶子都必须被选，选全部叶子也足够；$Need$ 是森林中所有有根叶子的数量，孤立节点也是叶子。

定义 $F_u(k)$ 为在 $u$ 的子树里选至多 $k$ 个节点，能覆盖的最多节点数，路径只延伸到 $u$ .定义边际收益为连续两项之差，只保留正收益。我们将证明它构成非增序列。

叶子的收益序列是 $[1]$ .对内部节点，假设各孩子的收益序列已非增。先把孩子们的序列合并并降序排列。取前 $k$ 项就能在总预算 $k$ 下获得孩子子树的最优收益：若取了某个孩子的较晚一项，却没取它前面不小的项，可以交换，所以始终能取成各孩子序列的前缀。

只要 $k\ge1$ ，节点 $u$ 还会被覆盖一次。因此 $u$ 的收益序列等于合并后的序列中**最大的一项加一**，其余项不变。加一后仍然非增。这同时证明了递推正确性和收益递减性质。

## 不必真的合并所有序列

一个子树的首项等于其高度（按节点数计）。为每个节点选取高度最大的一个孩子：将该孩子首项向上传递并加一；其他孩子的首项留下来，成为一段最终收益。更深处已经留下的收益也保留。叶子向上传递 $1$ ，整棵树的根再留下一项。

于是遍历所有节点，每个非最长孩子贡献它的高度，每棵树的根贡献自己的高度。这些数恰好是该树的完整边际收益多重集。无需线段树或重复删除根路径。

## 森林合并与最少树数

把所有树的收益项合并排序，前 $k$ 项的和就是第一个答案。标记每棵树的根所贡献的项为“首次使用该树”。它严格大于同一棵树的其他项：其他项都是某个真子树的高度，不超过整树高度减一。因此只要取到了某棵树的非首项，它的首项一定已经被取到。

同一收益值下，先取非首项，再取首项。证明这个规则能最小化树数：大于当前阈值的收益项都必须取；阈值处的非首项来自已经使用过的树，不增加树数，而每取一个首项都必须新增一棵树。尽量先取非首项正好使用最少的新树。较小的收益无法替换阈值项而仍保持最大覆盖数。

依次累加收益和首次使用标记，得到全部答案。虽然递推使用“至多”，前 $Need$ 次的边际收益都为正，所以相应最大值必能由恰好 $k$ 次选择实现。

## 实现与复杂度

按节点编号递增寻找未访问的连通分量，第一个遇到的节点就是该树的最小编号根。用显式遍历序列建立父子关系，再逆序求高度，避免五十万节点长链上的递归栈溢出。

建图与求高度为 $O(n)$ ，排序至多 $n$ 个收益项为 $O(n\log(n+1))$ ，空间为 $O(n)$ .独立对拍枚举小森林的所有选点集合，直接合并根路径，并逐预算比较覆盖数和树数。

## 程序与复现

参考程序见 [std.cpp](std.cpp)。使用 C++17 编译后，可用 `tests/generate.py --out-dir <题目目录以外的路径> --std <程序路径>` 生成输入和答案。固定种子与用例目的见 [生成计划](tests/plan.json)。性能测量见 [评测环境与性能](../../../docs/评测环境与性能.md)。