树链剖分分为两种：重链剖分、长链剖分。
其中重链剖分更为常见。
先来了解几个概念。
(1) 重儿子：对于一个非叶子节点，它儿子中，子树最大的是重儿子。
(2) 轻儿子：去重儿子以外的都是轻儿子。
(3) 重边：连着两个重儿子的边。
(4) 重链：重边组成的链。
(5) 链头：一条重链上最上面的节点，也就是深度最小的。
先 dfs 找到重儿子，并预处理子树大小，再 dfs 记录 dfs 序，链头。第二次 dfs 优先遍历重儿子，这样可以做到一条重链上的 dfs 序是连续的。
void dfs1(int x,int father)
{
dep[x]=dep[father]+1;//预处理深度
fa[x]=father;//预处理父亲
siz[x]=1;//计算子树大小
for(auto i:v[x])
{
if(i==father) continue;
dfs1(i,x);
siz[x]+=siz[i];
if(siz[son[x]]<siz[i]) son[x]=i;//找重儿子，并记录它的编号
}
}
void dfs2(int x,int topx)
{
id[x]=++cnt;//时间戳(dfs序)
a_new[cnt]=a[x];//新的a的值
top[x]=topx;//链头
if(!son[x]) return;//叶子节点，不用继续
dfs2(son[x],topx);//先遍历重儿子
for(auto i:v[x])
{
if(i==fa[x]) continue;
if(i==son[x]) continue;
dfs2(i,i);//没个轻儿子就是链头
}
}
然后来看模板题。
这个东西肯定是用数据结构维护，我们先按 dfs 建线段树。
先看和子树有关的两个操作，我们知道一个子树中的 dfs 是连续的，那么操作的区间是 id_x 到 id_x+siz_x-1 。
再看和链有关的两个操作， x 到 y 的链，我们令 x 所在重链深度更大，那么让 x 跳到链头，然后用线段树把这一段修改或记录答案，因为我们先遍历重儿子所以重链的 dfs 序都是连续的，然后我们跳到 x 的父亲处来到另一条重链，重复执行以上操作直到 x 和 y 处在同一条重链上，最后在维护一下 x 到 y 这片区间就行。
会跳几次呢？
可以注意到链头一定是轻儿子或根，因为如果是重儿子肯定可以继续往上。
因为是轻儿子所以它不可能达到父亲子树大小的一半，如果达到一半了，那么它肯定是重儿子，所以每次跳跃子树大小至少乘 2 ，所以跳不超过 O(\log_{2}n) 次，一般来说次数是接近 O(1) 的。
要用线段树维护所以最终时间复杂度是 O(q\log_{2}^{2}n) 。
四个操作的代码：
int query_chain_add(int x,int y)//链求和
{
int ans=0;
while(top[x]!=top[y])//如果两点所在的重链的不一样，也就是链头不一样
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);//强制x所在链的链头深度更大
ans+=query_add(1,n,id[top[x]],id[x],1);
//因为先遍历重儿子，所以重链dfs序也是连续的，跳到链头就将这个区间统计到和里
x=fa[top[x]];//跳到链头再跳到他的父亲，现在就在另一条重链上
}
if(dep[x]>dep[y]) swap(x,y);
ans+=query_add(1,n,id[x],id[y],1);//最后将x到y区间记录到答案中
return ans;//返回答案
}
int query_chain_max(int x,int y)//链最大值
{
int ans=-1e9;
while(top[x]!=top[y])//如果两点所在的重链的不一样，也就是链头不一样
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);//强制x所在链的链头深度更大
ans=max(ans,query_max(1,n,id[top[x]],id[x],1));
//因为先遍历重儿子，所以重链dfs序也是连续的，跳到链头就将这个区间统计到最大值里
x=fa[top[x]];//跳到链头再跳到他的父亲，现在就在另一条重链上
}
if(dep[x]>dep[y]) swap(x,y);
ans=max(ans,query_max(1,n,id[x],id[y],1));//最后将x到y区间记录到答案中
return ans;//返回答案
}
void update_tree(int x,int k)//修改子树
{
update(1,n,id[x],id[x]+siz[x]-1,1,k);//子树的dfs序是连续的
}
int query_tree(int x)//子树求和
{
return query_add(1,n,id[x],id[x]+siz[x]-1,1);//返回子树和，子树的dfs序是连续的
}