重链剖分

分解不变量 ​

根树中令 $size(v)$ 为子树大小；每个非叶节点选子树最大的一个孩子为重儿子，其余父子边为轻边。重边组成互不交的链，每条链按 DFS 顺序放到连续数组区间，并记录链顶 head。

若 $(v,u)$ 是轻边，则 $size(u)\le size(v)/2$：否则 $u$ 会比选中的重儿子更大，或两个孩子都大于一半而总大小超出 $v$。因此任意根叶路径每经过一条轻边，剩余子树至少减半，轻边数至多 $\lfloor {\log }_{2}n\rfloor$。

路径查询 ​

查询 $u$–$v$ 时，若两点链顶不同，把较深链顶一侧从 head 到节点的数组区间交给线段树公理库线段树Segment tree把区间递归分解为规范节点，并在每个节点保存幺半群聚合值的平衡树结构。，再跳到 head 的父亲；最终两点同链，处理最后区间。共拆 $O(\log n)$ 段，若每段查询 $O(\log n)$，总计 $O({\log }^{2}n)$。子树节点在 DFS 序中天然连续，子树查询通常只需一个区间。

非交换例子 ​

路径上拼接字符串或矩阵乘积时，$u$ 侧区间按向上方向，$v$ 侧按向下方向，不能把所有段任意交换。实现应分别维护左右累积器，并在会合时反转正确一侧；求和或最大值因交换律隐藏了这个错误。

失效边界 ​

HLD 是静态树分解；link/cut 改变子树大小后重儿子选择可能全局失效，应使用动态森林结构。重链条数本身可很多，受控的是一条根叶路径穿过的轻边数。链上 segment tree 的 lazy 标记、边权映射到较深端点及 LCA 端点是否计入都要统一。

构建与更新语义 ​

第一次 DFS 计算 parent、depth、size 和 heavy child；第二次从每个链顶沿重儿子连续编号，再递归轻儿子开新链。两遍都是 $O(n)$。点权修改只改一个数组位置，路径/子树区间修改交给线段树；这些不会改变拓扑，分解仍有效。

若值放在边上，常把边 $(parent(v),v)$ 映到较深端点 $v$ 的位置。查询 $u$–$v$ 时最终同链区间要排除 LCA 的位置，否则多计一条不存在的入边。这个差异不能靠线段树本身发现。

路径拆解的执行顺序 ​

查询 $u$ 到 $v$ 时，不直接寻找整条路径，而是反复比较两点所在重链链头的深度：

1. 若链头相同，最后处理同一重链上的一个连续区间；
2. 否则取链头更深的一侧，把该链头到当前点的区间交给底层结构；
3. 把当前点跳到链头父亲，继续比较；
4. 合并各段答案，并按路径方向处理非交换运算。

每次跨过轻边，剩余子树大小至少翻倍，因此每侧最多跳 $O(\log n)$ 条链。若每段用 segment tree 查询 $O(\log n)$，总时间 $O({\log }^{2}n)$；只有结合前缀表、可逆群操作或其他专门结构时才能再降一层。

边权常存到“较深端点”的数组位置。于是查询最后一段时要排除 LCA 对应位置，节点权则要保留；若不先固定这一映射，同一套区间端点会把 LCA 上方的一条边误算进来。

参考资料

• Daniel Sleator, Robert Tarjan, A Data Structure for Dynamic Trees, JCSS, 1983.
• Robert Tarjan, Data Structures and Network Algorithms, tree path decomposition.