# 粉碎者 题解

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

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


## 统一按边数计长度

题面已经按边数限制长度，直接取 $A=L$ 、$B=R$ . 当 $A=0$ 时必须考虑单节点路径。

令 $[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$ ，当且仅当它们属于不同分支。因此查询时排除当前端点所在分支即可。

同一分支里的两个端点不能在本轮相加，否则会把公共的一段计算两次，得到一条重复经过节点的路线。这些端点之间的合法简单路径会在后续子连通块中处理。

重心自身设置一个独立类别 $-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)。

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

边分治需先扩成 $2n-1$ 个点，并处理虚点、深度桶及边到点答案转换；本方案直接处理原树。星形树中，删中心后全是单点，本方案实际为 $O(n)$ ；边分治方案展开后的虚点链仍需多层边分治。操作统计还显示，随机树上边分治方案分治块大小之和约为本方案的 3.66 倍。因此，较高的通用最坏界可以和较低的实际耗时同时成立。

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