护林员 题解¶
解法与取舍¶
出题人解法：最长链收益与计数桶。 计数桶利用收益为整数且总和不超过 \(n-1\) 的性质，保证 \(O(n)\) 时间，是首选方案。比较排序的上界为 \(O(n\log(n+1))\) ；两者的实际耗时分析见下文。显式遍历可以处理百万节点长链。
程序与署名： std.cpp 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的比较排序见 alternative.cpp 和备用方案题解。
每日路线¶
这里的叶子指没有子节点的非根顶点。在树中，一天若要进入同一顶点的两个不同子树，就必须在进入第一个子树前、两个子树之间、离开第二个子树后各经过该顶点一次；根也不能在当天中途经过。因此每天只能沿一条从根向下的简单路径前进，再原路返回。若路径未到叶子，延长到某个叶子不会减少完成的任务数，也不会违反访问次数限制。
每天至多访问一个叶子，而每个叶子都有任务，所以至少需要叶子数那么多天。每个叶子安排一天即可达到下界。
最优前缀的边际收益¶
设 \(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\) 与最长孩子。根链收益为 \(h_1-1\) ，每个非最长孩子 \(v\) 开始的链收益为 \(h_v\) .把每个正收益 \(g\) 计入桶 \(\operatorname{cnt}[g]\) .
全部收益均为 \(1\) 到 \(n-1\) 的整数，按桶编号从大到小扫描，重复取出该桶数量的收益并输出累计和，即实现正文所需的降序排列。桶计数与扫描均为 \(O(n)\) ，加上遍历和输出，总时间 \(O(n)\) ，空间 \(O(n)\) .
理论复杂度与实际耗时¶
测量中，百万节点随机树的桶计数版约为 0.247 秒，比较排序版约为 0.254 秒。扩大到四百万节点的随机树后，两者仍接近。这并未推翻线性算法的最坏时间优势；需要看排序究竟处理多少元素，以及整份程序还做了什么。
排序的参数是叶子数¶
设叶子数为 \(D\) ，正收益为 \(g_1,\ldots,g_D\) .排序部分的界是 \(O(D\log(D+1))\) ，整个算法通常写为 \(O(n+D\log(D+1))\) 次基本操作；十进制输出还需处理实际输出字符。由于 \(D\le n-1\) ，才进一步概括成 \(O(n\log(n+1))\) .这不表示每个节点都要参加一次长度为 \(n\) 的排序。
收益链划分了全部非根节点，因此
于是收益至少为 \(t\) 的项数不超过 \((n-1)/t\) .叶子少时排序很小；叶子很多时平均收益很小。长链只有一项，星形树的所有收益都是一。现有百万节点用例的实际统计如下：
| 树形 | 收益项数 | 不同收益数 | 比较排序的比较次数 |
|---|---|---|---|
| 长链 | 1 | 1 | 0 |
| 星形 | 999,999 | 1 | 17,232,314 |
| 随机树 | 499,853 | 28 | 8,749,136 |
随机树中有 281,711 项收益为一，最大收益仅为 28。排序访问连续的整数数组，每次比较也只是两个整数的大小关系；没有每次比较再遍历一条树链的开销。重复值不保证当前比较排序变成线性时间：星形用例仍进行了约 1723 万次比较，不能把它当成零开销。
桶计数也有固定的线性成本¶
两份程序的读树、建邻接表、求父子关系和最长链、构造输出字符串等代码相同。计数版还会清零长度为 \(n\) 的桶数组，并扫描全部 \(n-1\) 个可能收益；排序版只排序实际收集的 \(D\) 项。因此，在长链等输入上，线性桶扫描甚至比只有一项的排序多做工作。
这些共同工作和不同常数会缩小整份程序的耗时比例。测量记录的是含读入、输出的总墙钟时间，未分别计时各阶段，故不能据此给出“输入输出占多少百分比”，也不能把差距全部归因于输入输出。上述收益和比较次数来自独立计数运行，不能用来推算各阶段的耗时占比。
为什么放大几倍仍难以区分¶
若叶子比例近似不变，规模乘四只让 \(\log_2 D\) 增加二；在已经接近百万的规模上，额外对数因子的相对变化不大。收益分布、共同开销和常数尚未让排序成为压倒性瓶颈时，放大几倍不足以自然产生几倍的速度差。桶计数仍给出更好的最坏界；这里的结论只解释已测输入，并不保证比较排序在所有数据或平台上都同样快。
针对排序选主元的构造¶
特殊排列能放大差距。把若干条路径接到根上，各路径长度就是对应的收益；固定最长路径在先，其余路径按需要编号，就能控制排序前的收益顺序，同时保持收益总和为 \(n-1\)。
在所测 GCC 16.2.0 的 libstdc++ 实现中，排序采用三点取中选主元。把少量较大的收益放在连续各轮的取样位置，其余收益全部置为一，可以让分区连续严重失衡，触发 introsort 的深度保护。四百万节点的构造只有 86 种收益，其中 3,996,256 项为一，却产生了 257,562,524 次排序比较。大量重复值本身并不能排除昂贵的比较排序。
| 节点数 | 计数桶中位数 (s) | 比较排序中位数 (s) | 排序 / 桶 |
|---|---|---|---|
| 1,000,000 | 0.152050 | 0.196939 | 1.30 |
| 2,000,000 | 0.290520 | 0.389631 | 1.34 |
| 4,000,000 | 0.578046 | 0.854063 | 1.48 |
每项计时重复七次；后两行仅为超出正式范围的性能实验。这个构造得到稳定且可测的差距，但排序耗时仍小于同一输入上桶计数耗时的两倍。按标程两倍余量、0.5 秒向上取整设置时限，仍无法可靠排除这份排序实现。该构造依赖具体选主元方式，不能推广为对所有排序库的结论。构造与压力数据由 Codex（GPT-6）提供，复现方法见树形构造与性能。
验证与性能¶
各方案的重复计时与峰值内存记录见评测环境与性能。