我们知道一颗树的dfs序可以有多种，所以可以通过一些暗箱操作把dfs序给安排了，从而能够更好的维护树上的区间信息
什么是树剖
树剖的核心是恰当的把树剖分成若干条链，链拼接起来就成了一段区间，然后利用数据结构来维护。
一些概念
重儿子：子树节点最多的儿子
轻儿子：重儿子以外的儿子
重边：父节点与重儿子所连的边
轻边：父节点与轻儿子所连的边
重链：重边组成的路径
轻链：轻边组成的路径
重链头：一条重链中深度最浅的点。特别地，与轻边相连的叶子节点也算重链头
图中加粗边为重边，红点为重链头
树链剖分流程
第一步，对这棵树进行dfs，处理出每个节点的父节点、深度、重儿子
void dfs1(int u)
{
size[u]=1; //size表示子树大小，初始size为1
for(int x=Root[u];x!=0;x=Next[x])
if(v[x]!=fa[u]){
d[v[x]]=d[u]+1;fa[v[x]]=u; //处理深度和父亲节点
dfs1(v[x]);size[u]+=size[v[x]]; //子节点size值处理后，更新父节点size
if(size[v[x]]>son[u])son[u]=v[x]; //取size最大的为重儿子
}
}
第二步，连接重边，形成重链，并记录新dfs序
void dfs2(int u,int t)//u为当前节点，t为u所在重链的重链头
{
id[u]=++tot,cur[tot]=a[u],top[u]=t; //处理dfs序和重链头
//id为时间戳，cur为新dfs序对应的值，top为重链头
if(son[u])dfs2(son[u],t);//先处理重儿子
//注意，重儿子和它的父节点都是同一个重链头
for(int x=Root[u];x!=0;x=Next[x])
if(v[x]!=fa[u]&&v[x]!=son[u])//如果是轻链底端，则自己做重链头
dfs2(v[x],v[x]);
}
至此，我们对树的剖分就结束了
经过剖分之后，我们发现这棵树就可以看成很多条链了
根据dfs序的性质我们可以知道，树链上的标号现在都是连续的，因此树上问题就被转化成了多个区间的问题，自然就可以想到用线段树来维护这颗被剖分好的树
线段树的使用方法和平常无异，只需注意一下build和引用函数时需要使用dfs序编号
void build(ll l,ll r,ll x)
{
c[x].l=l,c[x].r=r;
if(l==r){
c[x].sum=cur[l];// 这里是dfs序编号对应的值
return;
}
ll mid=(l+r)>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
update(x);
}
接下来我们看看树剖如何解决树上问题
以查询树上(x)到(y)的和为例
刚才的dfs维护了top数组
于是可以通过不断的向上跳到重链头，直到(x)和(y)位于一条重链，再用线段树查询出跳过的区间值。这样就可以(O(nlogn))的计算出(x)到(y)的和。
int calsum(int x,int y)
{
ll res=0;
while(top[x]!=top[y]){ //两点不在一条重链
if(d[top[x]]<d[top[y]]) //设x为深度较深的点
swap(x,y);
res+=query(id[top[x]],id[x],1); //对x所在重链求和
x=fa[top[x]]; //跳到重链头的父亲，也就是下一条重链上
}
if(d[x]>d[y])swap(x,y);
res+=query(id[x],id[y],1); //计算同一条重链上x到y的区间和
return res;
}
树剖求LCA
树剖后求LCA就很简单了，只需要跳重链头即可
int lca(int x,int y)
{
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]])
swap(x,y);
x=fa[top[x]];
}
if(d[x]>d[y])swap(x,y);
return x;
}
一些例题
树链剖分模板题
树剖+线段树综合应用
树剖修改题