1. 重链剖分

1.1. 简介

重链剖分将树分割成若干链维护信息，将树的结构转换为线性结构，然后可用其他数据结构维护。

定义以下概念：

重链剖分有以下性质：

1. 剖分时优先遍历重边，于是一条重链上的 DNF 序连续。
2. 一颗子树内 DFN 序连续。

根据这两条性质我们可以考虑维两节点路径上的信息，与一个子树内的信息。路径上的信息可以用若干重链信息拼接而成维护，子树内则直接用一定范围内连续 DFN 的节点信息维护即可。

重链剖分同时可以解决求 LCA 问题，当然，这在维护路径上信息时就需要用到。对于两个节点，考虑将深度大的节点跳转至其所在重链顶点的父节点，进行此操作若干次直到两者在一条重链上。最后一个一个跳转即可。

1.2. 具体实现

实现时，维护以下变量：

剖分操作需要进行两次 DFS：

• 第一次 DFS 维护 \(fa_i,dep_i,siz_i,hson_i\)。
• 第二次 DFS 维护 \(top_i,dfn_i,rk_i\)。