由于是在树上搞的 ds 所以考察数据结构本身性质偏多，需大力注重细节。

思想

考虑将一颗树的链划分成若干个区间进行维护。

这种划分方式叫做剖分。

约束

• 一颗有根树（有时要求换根但不是真正换根）

• 每个点恰好包含在一条剖出的链中（若被多条链同时包含则需要同时维护多条链，修改多余的可能影响复杂度）

• 剖分出来的链上面的节点深度有序

• 每条链的深度最大的端点为叶子节点

重儿子

决定了剖分的方式。

对于一个非叶子节点 \(u\)，恰好存在一个儿子 \(v\) 满足 \(u, v\) 在同一条链中，称 \(v\) 为 \(u\) 的重儿子，其他儿子称为轻儿子。

重边与轻边

上述 \((u, v)\) 的边为重边，其余边为轻边。

重儿子种类

下文默认 \(v\) 为 \(u\) 的重儿子。

一般有两种：

• \(v\) 为 \(u\) 的所有儿子中子树大小最大的

• \(v\) 为 \(u\) 所有儿子中子树中深度最大的

若多个 \(v\) 满足情况则任取一个。

重链剖分

设 \(u\) 的重儿子为 \(son_u\)。

每条由 \(u \to son_u\) 的链叫做重链。

性质

• 若 \(v\) 是 \(u\) 的轻儿子，那么有 \(sz_u > 2sz_v\)

• 任意节点到根的轻边数量为 \(O(\log n)\)

• 任意两点间的链上轻边数量为 \(O(\log n)\)

• 所有重链链顶节点子树大小之和为 \(O(n \log n)\)

• 重链上的节点 dfs 序连续

鸣谢

https://www.luogu.com.cn/article/e273yi3o