# 心灵终结仪：毛毛虫重链编号与区间集合

出题人解法：先编号重链，再编号其轻儿子根，最后编号这些轻子树的其余部分，使路径、外邻域和子树可分成少量区间。Codex（GPT-6）：用区间并集及差集整理边界、迭代预处理、64位懒标记、空集规则和验证。首选程序为 [std.cpp](std.cpp)。

## 编号次序

先求父亲、深度和子树大小，把最大子树的儿子选为重儿子。对一条重链，依次执行：

1. 链头已由父链编号；根1单独编号。把链头以外的重链顶点连续编号。
2. 按重链从上到下的次序，给每个顶点的所有轻儿子根编号，记录各自的区间 `Hair[u]` .
3. 仍按此顺序，递归处理各轻儿子所在重链，记录该顶点所有轻子树除根以外的编号区间 `Descendants[u]` .

因此一条链的非头部分连续，它的全部轻儿子根连续，各轻子树剩余部分也按挂接顶点的次序连续。空区间记录为左端点大于右端点，不能误用编号0。

预处理父亲和大小使用迭代遍历。编号递归只跨轻边，每次子树大小至少减半，所以深度为 $O(\log n)$ ，不会沿十万长链递归。

## 三类顶点集合

普通重链剖分把路径拆为 $O(\log n)$ 个同链段 $[u,v]$ .每段编号至多拆成链头单点和连续的剩余部分，共 $O(\log n)$ 个区间。

顶点 $u$ 的子树包括：从 $u$ 到当前重链尾的链段；这段的所有轻儿子根；这些轻子树除根以外的部分。后两类分别是一段编号区间，第一类至多两段，故子树至多需要四段。

外邻域的候选集合包括：每个路径链段挂接的轻儿子根、每段底端的重儿子，以及路径最低公共祖先的父亲。把这些区间合并，再减去整条路径的编号区间并集。

## 集合划分的证明

编号过程完整处理每个轻子树，且同链挂接位置的处理顺序一致，因此子树的三部分正好覆盖其全部后代，互不遗漏。

对于路径上任意顶点，其儿子分为轻儿子与重儿子。轻儿子都在候选集合中；一个同链段内部的重儿子已经在路径上，只有段底端的重儿子可能在路径外。路径顶点的父亲若不在路径上，只能是最低公共祖先的父亲。故所有外邻居都在候选集合中，候选中的非路径点也确实相邻。减去路径后得到恰好 $H(a,b)$ .

先合并区间、再作集合差，确保每个顶点只更新或累加一次。区间总数为 $O(\log n)$ ，排序合并及差集不会增加其渐进数量。

## 统一维护加、赋值、最大值与和

把顶点按编号映射到一维懒线段树。每个节点存和、最大值、待加值、待赋值及“有赋值”布尔标记。赋值 $v$ 时把和设为区间长度乘 $v$ ，最大值设为 $v$ ，清零待加值；加 $v$ 时分别增加长度乘 $v$ 、$v$ 和待加值。下传先赋值再加法，符合操作先后顺序。不能拿某个合法数值当作“没有赋值”的哨兵。

所有区间、标记及查询都遵循上述集合划分和线段树不变量，归纳得到全部12种操作正确。空区间列表的和为0，最大值输出 `EMPTY` .最大值可能为负数，初始聚合不能设为0。

## 复杂度与实现边界

预处理 $O(n)$ ；路径、邻域操作 $O(\log^2 n)$ ，子树操作 $O(\log n)$ ，空间 $O(n)$ .区间排序的 $O(\log n\log\log n)$ 被总体界包含。

单点权值绝对值不超过 $m10^8\le10^{13}$ ，总和绝对值不超过 $nm10^8\le10^{18}$ .标记、下传函数的参数及和都必须使用64位，不能仅把存储字段改为64位。显式集合差避免依赖易错的固定长度白名单及跨操作计数器。普通重链剖分只能压缩路径和子树，外邻域在星形树中可以包含线性多个分散顶点，不能直接逐个处理来满足本题规模。

## 验证与性能

正式数据各运行五次，并单独测量峰值内存。标准程序最慢中位数 0.403565 秒，峰值 29.02 MiB。按2倍向上取整至0.5秒，参考时限为 1 秒。

[测试说明](tests/README.md)、[环境](../../../docs/评测环境与性能.md)及[逐次测量和哈希](../../../docs/benchmark-R35.json)提供复现依据。其他环境需重新校准。