护林员题解¶

备用方案：比较排序。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\) 及重儿子。程序用 PathVertices[v] 保存 \(h_v\) ，名称强调按顶点数计数。迭代遍历避免在百万节点长链上递归爆栈。最后收集、排序重链收益并输出前缀和。

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

理论复杂度与实际耗时¶

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

完整的参数分析、操作统计和实测对照见主方案题解。