刚学会，打算整理一下，所以就写了这个帖子
树链剖分要解释清楚有点麻烦，如果你是来学习树链剖分的，还是需要看专业人士来讲
”近几年来，随着选手对数据结构问题的研究不断深入，留给出题人的命题空间也越来越狭小。因此，在国内的竞赛中，大部分数据结构问题除了在不停的包装原题老生常谈外，还有一种趋势是将经典的序列问题放到树结构或者仙人掌结构上，强行增加选手的代码量。我认为这种行为是非常无趣的，它破坏了很多数据结构问题简洁优美的性质，让题目变得索然无味。”
——吉如一
感觉这段话放在树链剖分上挺合适的……
树链剖分 就是把一棵树分成几条链，把树形变为线性，减少处理难度
所以树链剖分大致可以分成3个板块：
1.怎么把树变成线性的
2.将树变成线性后怎么操作
3.怎么操作&得到答案
我就按照这个顺序一个一个整理下去吧
转化
我暂时只会轻重链剖分，所以……
dfs1
int siz[M],deep[M],f[M],hson[M];
//结点数，深度，父结点，重儿子
void dfs1(int x,int fa){
siz[x]=1;
deep[x]=deep[f[x]=fa]+1;
for(int i:t[x])
if(i!=fa){
dfs1(i,x);
siz[x]+=siz[i];
if(siz[i]>siz[hson[x]]) hson[x]=i;
}
}
dfs2
int id[M],w[M],top[M],tim;
//结点对应的线性位置，线性位置对应的结点，所在链最顶端的结点，计数器
void dfs2(int x,int u){
top[x]=u;
id[x]=++tim;
w[tim]=x;
if(!hson[x]) return;
dfs2(hson[x],u);
for(int i:t[x])
if(i!=f[x]&&i!=hson[x])
dfs2(i,i);
}
挺模板的，只要不打错就行了
线性操作
变成线性后，我们就可以做很多东西了
主席树，平衡树，线段树，树状数组……
嗯，突然很烦有没有
没什么好说的，至少这些东西不应该在这里说（逃
只要不打错就行了（不可能的）
操作&统计答案
这一部分需要因地制宜了
大致可以分成单点操作，链式操作，树上操作
单点：没什么好说的，大家都会
树上：这个也很简单，同一棵树里面所有结点的时间戳都是连续的
比如以x为根结点的树上所有结点加上k
void add_tree(int x,LL k){
add(1,1,n,id[x],id[x]+siz[x]-1,k);
}
链式比较复杂，以加法为例子，我们再次细分
1.对x到y上所有点做加法
void add_chain(int x,int y,LL k){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
add(1,1,n,id[top[x]],id[x],k);
x=f[top[x]];
}
if(id[x]>id[y]) swap(x,y);
add(1,1,n,id[x],id[y],k);
}
2.对x到y上所有边做加法，我们把边的权值记录在边对应的儿子结点上，这个可以在dfs1中记录好，这时LCA(x,y)是不用参与加法的
void add_chain(int x,int y,LL k){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
add(1,1,n,id[top[x]],id[x],k);
x=f[top[x]];
}
if(x==y) return ;
if(id[x]>id[y]) swap(x,y);
add(1,1,n,id[x]+1,id[y],k);
}
说完了，总结一下，树链剖分是一个很难用的工具，目的旨在增加选手代码的码量（确信）