# 庆典计划 题解

## 解法与取舍

**出题人解法：重心分治与单调队列。** 单调队列方案保证 $O(n\log(n+1))$ 时间，是首选方案。线段树方案用区间查询完成端点配对，时间上界为 $O(n\log^2(n+1))$ ，作为备用。两种实现都使用显式遍历，避免长链上的深递归。

**程序与署名：** [std.cpp](std.cpp) 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的重心分治与线段树见 [alternative.cpp](alternative.cpp) 和[备用方案题解](solution-alternative.zh.md)。

## 长度与合法路径

题目按节点数限制长度，令 $A=L-1$ 、$B=R-1$ ，之后统一按边数处理。始终保留以节点 $1$ 为根的原父子关系。

对当前连通块选重心 $c$ .经过 $c$ 的向下路径，其上端点必须在原父亲链上，下端点必须在原后代中。上行收集不能拐入祖先的其他子树；下行只走原孩子。遇到已删除节点或深度超过 $B$ 即停止。两组都包含重心，重心的深度为零，路径和为 $v_c$ .

对端点 $x$ 记录深度 $d_x$ 及包含重心和端点的点权和 $s_x$ .与另一组端点 $y$ 配对需要

$$A-d_x\le d_y\le B-d_x,$$

收益为 $s_x+s_y-v_c$ .祖先和后代之间的两段只在重心相交，因此这些配对恰好是经过重心的合法向下路径。

## 单调移动的深度窗口

先对另一组各深度记录最大路径和 $M[d]$ .祖先链天然按深度排列，后代使用广度优先遍历，当前组也按深度递增处理。对深度 $d_x$ ，查询区间为

$$[\max(0,A-d_x),\ \min(D,B-d_x)],$$

其中 $D$ 为另一组最大深度。随着 $d_x$ 增大，左右端点都不增。用单调队列维护窗口最大值：从大深度向小深度加入新位置，删除比当前右端点大的旧位置；队尾被新值支配的候选可直接删除。每个深度至多入队、出队一次，所有查询合计线性时间。空窗口不产生候选。

祖先对后代、后代对祖先各处理一遍，得到每个端点 $x$ 的最优完整路径收益 $g_x$ .重心同时出现于两组不会重复计权，因为公式只保留一份 $v_c$ ；若 $A=0$ ，单点路径也被纳入。

## 从端点向内部传播

收集时记录朝向重心的父记录。将每个端点的标记置为 $g_x$ ，再逆遍历顺序向父记录取最大值。

每个候选路径都包含从 $x$ 到重心的整段，故传播不引入不经过当前点的路径。反过来，任意经过重心并包含点 $u$ 的合法路径，都有一端位于以重心为根时 $u$ 的子树中；该端点的最优候选不小于此路径，并会传播到 $u$ .因此本轮对每个点取得了所有经过重心的合法路径的最优值。

删除重心后，继续处理各个剩余连通块。任意路径在首次遇到位于它上面的分治重心时被处理，因而所有路径均被覆盖。

## 实现与复杂度

大小为 $s$ 的连通块用 $O(s)$ 时间寻找重心、收集、处理窗口和传播答案。每次剩余块至多为原块一半，总时间 $O(n\log(n+1))$ ，空间 $O(n)$ .原树遍历和分治调度均使用显式数组或栈。至多八个点的小块直接枚举合法祖先路径，是常数规模的终止情形，不改变复杂度。

路径和使用 64 位整数；无解标记不参与加法。负权路径不能用零代替，最终仅对确实无解的点输出 `-1061109568` .

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

测量中的五十万节点随机树上，单调队列版约为 0.741 秒，线段树版约为 0.816 秒；两百万节点随机树上分别约为 4.015 和 4.391 秒。差距小的关键是：最坏界中的两个对数并不在每个输入、每个查询上同时取满。

### 查询的值域是深度

对一个分治块，设收集到的端点记录数为 $m_c$ ，最大深度为 $D_c$ .备用程序按深度建树，树的叶子数取覆盖 $0$ 到 $D_c$ 的二次幂。因此线段树部分更具体的上界为

$$O\bigl(D_c+1+m_c\log(D_c+2)\bigr).$$

不能把每次查询都当成 $\log n$ 层。星形树的深度范围很小；平衡树和测量中的随机树也比较浅；长度上限还会截断端点收集。深链可以让深度与块大小同阶，使这一对数接近 $\log n$ ；浅树的实际值则可能小得多。结合重心分治层数，才得到通用的 $O(n\log^2(n+1))$ 界。

此外，查询区间与 $[0,D_c]$ 取交后可能为空。程序此时不进入查询循环；单点区间只处理一个叶子。分治到小块后，若最长可能路径已短于 $L$ ，也会出现大量空查询。对于非空区间，迭代查询每轮将两个下标右移一位，实际合并的规范区间数也依赖端点对齐方式。

### 执行次数能看出哪些差别

下面统计的是当前备用程序所有分治轮次合计的查询，而非只统计最上层；“循环轮数”是 `while (Left < Right)` 的实际执行次数，不是机器指令数。

| 五十万节点用例 | 所有轮次最大深度 | 查询数 | 空查询数 | 查询循环总轮数 |
| --- | ---: | ---: | ---: | ---: |
| 随机树、完整长度范围 | 29 | 4,306,142 | 0 | 16,692,524 |
| 长链、节点长度 100000–250000 | 249,999 | 8,975,731 | 7,775,730 | 18,840,416 |
| 正权长链、完整长度范围 | 250,000 | 8,975,732 | 0 | 86,738,817 |

随机树平均每次查询只有约 3.88 轮。长链窗口用例虽很深，却有约 86.6% 的查询直接为空。最后一行说明深链加宽窗口确实增加了额外工作，不能因为已有计时接近就否认复杂度差异。

这里的随机树特指随题生成器逐点连接已有父节点、再重新编号得到的用例；这些深度统计不能推广到所有随机生成方式。

### 多一个对数不等于整份程序慢一个对数倍

两版都需要反复遍历连通块、寻找重心、收集端点及传播答案。单调队列方案也要构造各深度最大值数组，分别处理祖先与后代两个方向；“每块线性”仍包含多次扫描、初始化和分配。线段树方案在连续数组上进行迭代查询。当前编译环境中，两版端点记录分别为 32 和 24 字节，这也造成存储常数差异；较小记录可能减少内存传输，但没有缓存命中率测量，不能将其当成已定位的耗时占比。

记录缩小、共同工作及每块实际深度解释了为何理论差异未直接变成巨大时间差。[操作统计](../../../docs/performance-work-P1.json)核实的是循环次数；总计时不能确定每一项各占多少时间。规模乘四也只让 $\log_2 n$ 增加二，并没有让额外对数因子乘四。单调队列的最坏界更好，线段树方案也能在当前测量数据与时限下通过；这两个结论并不矛盾。

### 针对深度和查询窗口的构造

长链配宽窗口可以同时增加分治深度与有效查询数；梳形树、细分二叉树和双扫帚树还能改变同一深度上的端点数量。长度上限取约 $n/3$、$n/2$ 或二次幂附近的值，用于检查区间分解与端点对齐的影响。权值另覆盖随机、全正、全零和正负交替。

在齿长为七的梳形树上，五十万节点时，单调队列与线段树的七次计时中位数分别为 0.369029 和 0.430357 秒，后者约慢 17%。扩大到一百万、两百万节点，五次计时的比例分别为 1.24 和 1.18。双扫帚树的差距也只有约一成，仍不足以在保留两倍标程余量时稳定区分通过与超时。

树形之外，编号也会影响当前实现的实际耗时。五十万节点随机重编号长链、节点长度范围 $[1,249997]$ 的一份输入上，两者分别为 1.742455 和 1.356307 秒，反而是单调队列更慢。重编号不改变树的数学结构，却会改变按编号存储的数组访问位置；这与局部性影响相符，但没有缓存采样，不能把全部差异归因于缓存。

这些定向构造及两倍、四倍规模实验尚未找到可靠排除线段树实现的输入，也不能证明所有合法构造都无法做到。压力数据由 Codex（GPT-6）提供，具体参数、重复计时与时限校准见[树形构造与性能](../../../docs/树形构造与性能.md)。

## 验证与性能

各方案的重复计时与峰值内存记录见[评测环境与性能](../../../docs/评测环境与性能.md)。