心灵终结仪：毛毛虫重链编号与区间集合¶
出题人解法：先编号重链，再编号其轻儿子根，最后编号这些轻子树的其余部分，使路径、外邻域和子树可分成少量区间。Codex（GPT-6）：用区间并集及差集整理边界、迭代预处理、64位懒标记、空集规则和验证。首选程序为 std.cpp。
编号次序¶
先求父亲、深度和子树大小，把最大子树的儿子选为重儿子。对一条重链，依次执行：
- 链头已由父链编号；根1单独编号。把链头以外的重链顶点连续编号。
- 按重链从上到下的次序，给每个顶点的所有轻儿子根编号，记录各自的区间
Hair[u]. - 仍按此顺序，递归处理各轻儿子所在重链，记录该顶点所有轻子树除根以外的编号区间
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 秒。