树剖是把一棵树拆成一堆链，\(O(logn)\)地跳链，用一些数据结构维护每条链，从而实现增加1k代码而降低复杂度到\(O(log^2n)\)的效果。
树链剖分大概分三种：长链剖分，实链剖分和重链剖分。一般说树剖就是重链剖分。
如何把树拆成链？我们定义一个节点的重子节点是它子树最大的儿子，其余的为轻子节点。于是我们把一个节点与它的所有重儿子连成链。
重子节点所组成的链叫重链。显然，一条链的起点一定是轻子节点。于是我们成功把树剖了。
接下来是如何维护这些链的问题。我们树上套数据结构常用dfs序。这个也是，只要我们求dfs序的时候从重子节点开始搜索，就可以保证重链上的dfs序是连续的。
//找重儿子
void dfs1(int x,int f,int d){
fa[x]=f;dep[x]=d;size[x]=1;son[x]=0;//我们需要存每个节点的重儿子和父亲
int maxsize=0;
for(int i=head[x];i;i=edge[i].next){
if(!dep[edge[i].v]){
dfs1(edge[i].v,x,d+1);
size[x]+=size[edge[i].v];
if(maxsize<size[edge[i].v]){
maxsize=size[edge[i].v];
son[x]=edge[i].v;//dfs找重儿子
}
}
}
}
//连重链
void dfs2(int x,int f){
dfn[x]=++num;top[x]=f;rnk[num]=x;
wei[num]=val[x];
if(son[x])dfs2(son[x],f);//每次搜索优先从重儿子开始 保证了重链上的dfs序连续
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=son[x]&&edge[i].v!=fa[x])dfs2(edge[i].v,edge[i].v);
}
}
dfs1(1,0,1);dfs2(1,0);build(1,1,n);
然后是树上的修改与查询。（其实差不太多）
关于修改，我们每次大概可以找到树上要修改的链上的lca。于是我们每次修改该点所在的一条链然后往上面一条链上跳，一直跳到同一条链。具体见注释。
void change(int x,int y,int val){
while(top[x]!=top[y]){//不在同一条链上
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,dfn[top[x]],dfn[x],val);//修改当前链
x=fa[top[x]];//往上跳
}
if(dep[x]>dep[y])swap(x,y);
update(1,dfn[x],dfn[y],val);//在同一条链上 直接修改
}
int querysum(int x,int y){
int num=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
num+=query(1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
num+=query(1,dfn[x],dfn[y]);
return num;
}
然后对子树整体的操作，我们之前dfs序的时候整棵子树的dfs序都连续，所以直接改就行。
query(1,dfn[x],dfn[x]+size[x]-1)