# 庆典计划 题解

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

解法贡献：Codex（GPT-6）基于树的重心分治和线段树，整理了按深度排除同类端点、向路径内部传播答案的实现与证明；使用显式遍历支持长链。重心分治、线段树均为已有方法。


## 统一按边数计长度

题目限制的是节点数。包含 $t$ 个节点的路径恰有 $t-1$ 条边，所以取 $A=L-1$ 、$B=R-1$ . 必须保留以节点 $1$ 为根的原父子关系，不能随分治重心改变行进方向。

令 $[A,B]$ 为允许的边数区间。给一个连通块选重心 $c$ ：删除它后，每个剩余连通块的大小都不超过原来的一半。合法路径要么经过 $c$ ，要么完全位于删除 $c$ 后的一个连通块。处理前一类，再分别处理后一类。

## 经过重心的合法端点

对可用端点 $x$ ，记录到重心的边数 $d_x$ ，以及包含两端的路径点权和 $s_x$ . 端点 $x,y$ 组合出的收益为

$$s_x+s_y-v_c$$

长度条件为

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

一条向下路径经过 $c$ 时，上端点只能是 $c$ 的祖先，下端点只能是 $c$ 的后代。把所有严格后代标为类别 $0$ ，所有严格祖先标为类别 $1$ . 配对时排除与当前端点相同的类别。

收集类别 $0$ 时遍历当前连通块中重心下方的各棵子树。收集类别 $1$ 时只能沿原父亲链向上走，不能拐进某个祖先的其他孩子分支。此前已删除的节点会截断遍历。不同后代分支之间即使能经过重心连通，也不能组成始终向下的路径。

重心自身设置一个独立类别 $-1$ ，深度为 $0$ ，路径和为 $v_c$ . 对于非重心端点，允许另一端是重心。查询重心本身时不排除任何类别；若长度允许零条边，它也可以和自己配对，收益恰为 $v_c$ .

深度超过 $B$ 的端点不能参与经过重心的合法路径，可以停止这一方向的收集。它仍会进入后续的分治连通块。

## 每个深度保留两个不同类别

对每个深度，把各个类别中的最大路径和作为候选。只保留值最大的两个**不同类别**，在线段树合并时仍执行同样的操作。

为什么两个足够？一次查询只会排除一个类别。如果区间最大值不属于被排除类别，就直接取它；否则取另一类别的最大值。每个子区间都只需提供自己的前两个不同类别，任何被丢弃的候选都不可能成为合并后所需的答案。两名候选的值可以相同，但类别必须不同。

于是对端点 $x$ ，在线段树中查询

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

其中 $D$ 是本次收集到的最大深度。空区间或没有可用类别时，不产生候选；否则得到一个以 $x$ 为端点、经过 $c$ 的最大路径收益 $g_x$ .

## 更新整条路径上的节点

只更新端点会漏掉路径内部的节点。把本次收集的节点按以 $c$ 为根的遍历记录父亲，先将节点标记设为 $g_x$ ，再逆序遍历，让父亲取自己和孩子标记的最大值。

每个 $g_x$ 对应的路径都包含从 $x$ 到 $c$ 的整段。因此，把它向父亲传播是合法的。另一方面，任意经过 $c$ 且包含节点 $u$ 的合法路径，至少有一个端点在 $u$ 的这棵局部子树里；该端点的候选不小于这条路径的收益，所以也会传播到 $u$ . 由此，本轮得到每个节点在所有经过 $c$ 的合法路径中的最优值。

对每个节点取所有分治轮次的最大值。任意路径第一次遇到被删除的重心时，要么正好经过该重心，要么继续保留在唯一的子连通块中，因此不会遗漏。

## 实现与复杂度

设当前连通块大小为 $s$ . 用显式数组遍历计算父亲、子树大小和重心，再收集端点。线段树建立与标记传播花费 $O(s)$ ，区间查询共 $O(s\log(s+1))$ .

重心分治最多有 $O(\log(n+1))$ 层，总时间为 $O(n\log^2(n+1))$ ，空间为 $O(n)$ . 参考程序将待处理连通块放进栈中，原树遍历没有递归调用。当前连通块的临时数组在处理结束后释放。

路径收益的绝对值不超过 $1000n$ . 实现使用一个比所有合法收益更小的内部标记，不把该标记参与加法；最后将仍无答案的节点输出为 `-1061109568` . 负收益不应替换成零。

## 验证

小规模检查直接枚举合法路径，逐节点更新收益。随机树、链、星形树、单节点、负权和无法满足长度的情况均已覆盖。最大规模测试另检查显式遍历与内存使用，详见[评测环境与性能](../../../docs/评测环境与性能.md)。

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

线段树建立在收集到的深度范围上，查询上界实际为 $O(\log(D_c+2))$ .浅树、小分治块、长度截断和空区间都降低实际开销：五十万节点随机树的查询循环平均仅约 3.88 轮；长链窗口用例约 86.6% 的查询直接为空。单调队列方案也有共同遍历与多次线性扫描，故不能把额外对数直接当成整份程序的耗时倍数。

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