# 护林员题解

> 备用方案：比较排序。Codex（GPT-6）采用的解法，程序见 [alternative.cpp](alternative.cpp)；与出题人解法的比较见[主题解](solution.zh.md)。


## 每日路线

这里的叶子指没有子节点的非根顶点。在树中，一天若要进入同一顶点的两个不同子树，就必须在进入第一个子树前、两个子树之间、离开第二个子树后各经过该顶点一次；根也不能在当天中途经过。因此每天只能沿一条从根向下的简单路径前进，再原路返回。若路径未到叶子，延长到某个叶子不会减少完成的任务数，也不会违反访问次数限制。

每天至多访问一个叶子，而每个叶子都有任务，所以至少需要叶子数那么多天。每个叶子安排一天即可达到下界。

## 最优前缀的边际收益

设 $F_v(0)=0$ ，$F_v(k)$ 是在以 $v$ 为根的子树中，选择至多 $k$ 条从 $v$ 到叶子的路径时，最多能覆盖的顶点数。只考虑直到所有叶子都被选中的那些正边际收益 $F_v(k)-F_v(k-1)$ .

叶子的收益序列只有一个 $1$ . 假设各子节点的收益序列均非增：为子树分配路径名额时，选择某个子树的第 $t$ 份收益，就必须同时选择它前面的 $t-1$ 份。因此可以按从大到小的顺序合并所有子树的收益，相等时保持同一子树中的先后顺序。取合并序列的前 $k$ 项，总能满足这个前缀条件，也取得最大的收益和。

只要选择了至少一条路径，还会覆盖 $v$ 本身。因此，把合并序列的第一项加 $1$ ，就得到 $v$ 的收益序列。它仍然非增，且第一项等于从 $v$ 到最深叶子的顶点数。归纳成立。

记 $h_v$ 为从顶点 $v$ 向下到某个叶子的最长路径所包含的顶点数，两端点都计入，因此叶子的 $h_v=1$ . 对每个顶点选择 $h_v$ 最大的子节点作为“重儿子”。从根到最深叶子的首条重链带来 $h_1-1$ 个任务。每个非重儿子 $v$ 开始一条新的重链，其边际收益为 $h_v$ . 将这些值从大到小排序，依次求前缀和，就是每天结束时的最优累计任务数；值的个数恰好为叶子数。

上述合并过程每次只为某个子树追加一条路径，不撤回先前的选择。因此可以得到一个叶子的排列，其前 $k$ 条路径对所有 $k$ 都最优；排列完全部叶子时恰好用完最少天数 $D$ . 根本身没有任务，所以根的第一份收益要减 $1$ ，其余收益不变。这也解释了程序中首条重链的特殊处理。

## 实现与复杂度

先用迭代遍历确定父节点和遍历顺序，再逆序计算各节点的 $h_v$ 及重儿子。程序用 `PathVertices[v]` 保存 $h_v$ ，名称强调按顶点数计数。迭代遍历避免在百万节点长链上递归爆栈。最后收集、排序重链收益并输出前缀和。

时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n)$ .

## 理论复杂度与实际耗时

排序实际只处理叶子数 $D$ 那么多项，收益又满足总和为 $n-1$ ；长链只有一项，星形全部为一。两份程序共有的读入、遍历和输出，以及计数版完整桶扫描的成本，会缩小总耗时差距。重复值并不保证比较排序成为线性时间：百万节点星形仍实测执行约 1723 万次比较。

完整的参数分析、操作统计和实测对照见[主方案题解](solution.zh.md#理论复杂度与实际耗时)。