树链剖分一般用来求树上区间查询、修改 或 求LCA
学习树链剖分之前要学会线段树
树链剖分需线段树维护
首先弄清几个名字
| 重儿子 | 所有儿子中，子树大小最大那个儿子 |
| 轻儿子 | 除重儿子以外的儿子 |
| 重边 | 连接重儿子的边 |
| 轻边 | 连接轻儿子的边 |
| 重链 | 由重边组成的路径 |
| 轻链 | 由轻边组成的路径 |
举个例子：
剖分过程要计算的值
| father[i] | i在树中的父亲 |
| d[i] | i在树中的深度 |
| size[i] | i的子树大小 |
| son[i] | i的重儿子 |
| top[i] | i在的重路径的顶部 |
| seq[i] | i结点在线段树中的位置 |
| rev[i] | 线段树的第i个位置在树中的位置 |
预处理
两遍dfs
第一遍dfs求出前四个值
void dfs1(int u,int fa) { father[u]=fa; d[u]=d[fa]+1; size[u]=1; for (int i=h[u];i!=0;i=e[i].next) { int v=e[i].to; if (v==fa) continue; dfs1(v,u); size[u]+=size[v];//累加字数个数 if (size[v]>size[son[u]]) son[u]=v;//存下重儿子 } }
第二遍dfs求出后三个值
void dfs2(int u,int fa) { if (son[u]) { seg[son[u]]=++cnt;//存下位置 top[son[u]]=top[u]; rev[cnt]=son[u]; dfs2(son[u],u); } for (int i=h[u];i!=0;i=e[i].next) { int v=e[i].to; if (!top[v]) { seg[v]=++cnt; rev[cnt]=v; top[v]=v; dfs2(v,u); } } }
查询
查询（u，v）的LCA，选则两点深度更深的往上跳，直到 u==v;
假设u，v不在同一条重链上，那么可以直接跳到father[top[u/v]];
调过的是一段区间，所以还要记录区间[seg[u/v],seg[top[u/v]]];
当u，v的top相同时，表示他们在同一重链上，那么u，v深度最小的就是原路径的LCA
void ask(int l,int r) { int fl=top[l],fr=top[r]; while (fl!=fr) { if (d[fl]<d[fr]) swap(l,r),swap(fl,fr); query(1,1,cnt,seg[fl],seg[l]); l=father[fl],fl=top[l]; } if (d[l]>d[r]) swap(l,r); query(1,1,cnt,seg[l],seg[r]); }