重链剖分

定义

• 重子节点 表示其子节点中子树最大的子节点（之一）。如果没有子节点，就无重子节点。
• 轻子节点 表示剩余的所有子节点。
• 从这个节点到重子节点的边为 重边。
• 从这个节点到其他轻子节点的边为 轻边。
• 若干条首尾衔接的重边构成 重链。把落单的节点也当作重链，那么整棵树就被剖分成若干条重链。

性质与应用

可以发现，当我们向下经过一条 轻边 时，所在子树的大小至少会是原子树的一半。因此，对于树上的任意一条路径，把它拆分成从 LCA 分别向两边往下走，分别最多走 $O(\log n)$ 次，因此，树上的每条路径都可以被拆分成不超过 $O(\log n)$ 条重链。单次操作的时间复杂度为 $O(\log^2n)$。

同时，每条链上的点深度互不相同，保证划分出的每条链上的节点 DFS 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。

而 DFS 序满足每棵子树的序号都连续，这样便可以快速处理对于链和子树的区间修改、查询问题。

例题

例题：重链剖分与树的路径覆盖问题