目录
树链剖分
基础概念
重儿子：父节点的所有儿子中子树节点数目最多的节点
轻儿子：父节点除重儿子以外的节点
重边：父节点和重儿子连成的边
轻边：父节点和轻儿子连成的边
重链：由多条重边连接而成的路径
如下图，绿色边即为重边
性质
1.整棵树会被剖分成若干条重链（可以将单独的叶子节点看作一条重链）
2.轻儿子一定是每条重链的顶点
3.任意一条路径被切分成不超过 \(\log n\) 条链
用到的 5 个数组：
-
fa[u]：存节点 u 的父节点
-
dep[u]：存节点 u 的深度
-
son[u]：存节点 u 的重儿子
-
sz[u]：存以节点 u 为根的子树的节点个数
-
top[u]：存 u 所在的重链的顶点，即链头
利用两个 dfs 处理这五个数组（4 + 1）
（下面是用邻接表实现的）
dfs1 ：预处理数组 dep、sz、fa、son，初始为 dfs1 (根节点， 0)
从根开始遍历每个节点，统计深度、父节点和节点数初值，最主要就是递归后判断重儿子的位置
void dfs1(int u, int f){//预处理dep、sz、fa、son
dep[u] = dep[f] + 1;
sz[u] = 1;
fa[u] = f;
for(auto v : e[u]){
if(v == f) continue;
dfs1(v, u);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
return ;
}
dfs2 ：预处理数组 top，初始为 dfs2 (根节点，根节点)
首先赋值链头，如果没有重儿子直接返回，再 dfs 重儿子（重儿子的链头是当前的链头），最后遍历轻儿子，但是轻儿子的链头是自己
void dfs2(int u, int t){//预处理top
top[u] = t;
if(!son[u]) return ;
dfs2(son[u], t);
for(auto v : e[u]){
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
return ;
}