庆典计划 题解¶
备用方案：重心分治与线段树。Codex（GPT-6）采用的解法，程序见 alternative.cpp；与出题人解法的比较见主题解。
解法贡献：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\) 组合出的收益为
长度条件为
一条向下路径经过 \(c\) 时，上端点只能是 \(c\) 的祖先，下端点只能是 \(c\) 的后代。把所有严格后代标为类别 \(0\) ，所有严格祖先标为类别 \(1\) . 配对时排除与当前端点相同的类别。
收集类别 \(0\) 时遍历当前连通块中重心下方的各棵子树。收集类别 \(1\) 时只能沿原父亲链向上走，不能拐进某个祖先的其他孩子分支。此前已删除的节点会截断遍历。不同后代分支之间即使能经过重心连通，也不能组成始终向下的路径。
重心自身设置一个独立类别 \(-1\) ，深度为 \(0\) ，路径和为 \(v_c\) . 对于非重心端点，允许另一端是重心。查询重心本身时不排除任何类别；若长度允许零条边，它也可以和自己配对，收益恰为 \(v_c\) .
深度超过 \(B\) 的端点不能参与经过重心的合法路径，可以停止这一方向的收集。它仍会进入后续的分治连通块。
每个深度保留两个不同类别¶
对每个深度，把各个类别中的最大路径和作为候选。只保留值最大的两个不同类别，在线段树合并时仍执行同样的操作。
为什么两个足够？一次查询只会排除一个类别。如果区间最大值不属于被排除类别，就直接取它；否则取另一类别的最大值。每个子区间都只需提供自己的前两个不同类别，任何被丢弃的候选都不可能成为合并后所需的答案。两名候选的值可以相同，但类别必须不同。
于是对端点 \(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 . 负收益不应替换成零。
验证¶
小规模检查直接枚举合法路径，逐节点更新收益。随机树、链、星形树、单节点、负权和无法满足长度的情况均已覆盖。最大规模测试另检查显式遍历与内存使用，详见评测环境与性能。
理论复杂度与实际耗时¶
线段树建立在收集到的深度范围上，查询上界实际为 \(O(\log(D_c+2))\) .浅树、小分治块、长度截断和空区间都降低实际开销：五十万节点随机树的查询循环平均仅约 3.88 轮；长链窗口用例约 86.6% 的查询直接为空。单调队列方案也有共同遍历与多次线性扫描，故不能把额外对数直接当成整份程序的耗时倍数。
完整的参数分析、操作统计和实测对照见主方案题解。