基础知识详见这篇：banananana：树链剖分原理和实现
请务必看完！写的很棒，学习了！
根据上面博客的讲解，树链剖分会得到几个很重要的数组
第一次dfs得到：
\[fa[i],dep[i],sz[i],son[i]\]
分别表示 父亲节点、深度、子树大小、重节点
第二次dfs得到：
\[id[i],rnk[i],top[i]\]
分别表示 节点序号对应的dfs序、dfs序对应的节点序号、链的顶端（若此节点为重节点，则为重链的顶端；若为轻节点，则为自身）
这里的dfs序大有讲究：由于在第二次dfs保证优先对重节点进行dfs，所以一条重链上所有节点的dfs序相邻（性质1）
同时，树链剖分保证：对于任意一个节点，若想回到原点，最多只需经过logN条链（性质2）
通过这两条性质，如果我们想对树上的一条路径进行某些计算，我们最多只需要枚举O(logN)级别的数量的链；而由于链的dfs序相邻，我们可以使用数据结构帮助我们高效完成计算
最基本的应用是求LCA
虽然用倍增比较方便，但是写一写树剖的实现有助于加深理解
比较让人担心的一种情况是，LCA恰好在一条重链上，同时x、y其中有点需要经过这条链
我们有一种办法可以避免“跳过头”，就是比较两个点向上跳一条链后的深度，选择跳一条链后较深的进行跳转
而找到LCA的条件是：x、y位于同一条重链上（即top[x]==top[y]），那么LCA为深度较低的点
LCA模板题：洛谷P3379（【模板】最近公共祖先）
（用vector存边就乖乖开O2吧）
#include <cstring> #include <cmath> #include <cstdio> #include <vector> using namespace std; const int N=500005; int n,m,root; vector<int> v[N]; int fa[N],dep[N],sz[N],son[N]; inline void dfs1(int x,int f) { sz[x]=1; fa[x]=f; dep[x]=dep[f]+1; for(int i=0;i<v[x].size();i++) { int next=v[x][i]; if(next==f) continue; dfs1(next,x); sz[x]+=sz[next]; if(!son[x] || sz[son[x]]<sz[next]) son[x]=next; } } int cnt; int id[N],rnk[N],top[N]; inline void dfs2(int x,int t) { top[x]=t; id[x]=++cnt; rnk[cnt]=x; if(son[x]) dfs2(son[x],t); for(int i=0;i<v[x].size();i++) { int next=v[x][i]; if(next==fa[x] || next==son[x]) continue; dfs2(next,next); } } inline int lca(int x,int y) { while(top[x]!=top[y]) if(dep[top[x]]>dep[top[y]]) x=fa[top[x]]; else y=fa[top[y]]; return (dep[x]<dep[y]?x:y); } int main() { // freopen("input.txt","r",stdin); scanf("%d%d%d",&n,&m,&root); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } dfs1(root,0); dfs2(root,root); while(m--) { int x,y; scanf("%d%d",&x,&y); printf("%d\n",lca(x,y)); } return 0; }
一道模板题：洛谷P3384 （【模板】树链剖分）
求和利用的是区间和线段树，修改用懒标记即可
操作1、2：注意利用两条性质，对于每条链分开处理；单次复杂度O((logN)2)
操作3、4：多记录一个离开节点i的dfs序（按理说这个应该更基础点吧）；单次复杂度O(logN)
#include <cstring> #include <cmath> #include <cstdio> #include <vector> using namespace std; typedef long long ll; const int N=100005; int n,m,root,P,size=1; vector<int> v[N]; int fa[N],dep[N],sz[N],son[N]; inline void dfs1(int x,int f) { sz[x]=1; fa[x]=f; dep[x]=dep[f]+1; for(int i=0;i<v[x].size();i++) { int next=v[x][i]; if(next==f) continue; dfs1(next,x); sz[x]+=sz[next]; if(!son[x] || sz[son[x]]<sz[next]) son[x]=next; } } int cnt; int id[N],rid[N],rnk[N],top[N]; inline void dfs2(int x,int t) { top[x]=t; id[x]=++cnt; rnk[cnt]=x; if(son[x]) dfs2(son[x],t); for(int i=0;i<v[x].size();i++) { int next=v[x][i]; if(next==fa[x] || next==son[x]) continue; dfs2(next,next); } rid[x]=cnt; } int val[N]; int t[N<<2],len[N<<2],tag[N<<2]; inline void Build(int k,int l,int r,int a,int b) { if(a>r) return; if(a==b) { t[k]=val[rnk[a]];//*** len[k]=1; return; } int mid=(a+b)>>1; Build(k<<1,l,r,a,mid); Build(k<<1|1,l,r,mid+1,b); t[k]=(t[k<<1]+t[k<<1|1])%P; len[k]=len[k<<1]+len[k<<1|1]; } inline void Update(int k) { if(!tag[k]) return; tag[k<<1]=(tag[k<<1]+tag[k])%P; t[k<<1]=(t[k<<1]+(ll)len[k<<1]*tag[k])%P; tag[k<<1|1]=(tag[k<<1|1]+tag[k])%P; t[k<<1|1]=(t[k<<1|1]+(ll)len[k<<1|1]*tag[k])%P; tag[k]=0; } inline void Modify(int k,int l,int r,int a,int b,int x) { if(a>r || b<l) return; if(a>=l && b<=r) { tag[k]=(tag[k]+x)%P; t[k]=(t[k]+(ll)len[k]*x)%P; return; } Update(k); int mid=(a+b)>>1; Modify(k<<1,l,r,a,mid,x); Modify(k<<1|1,l,r,mid+1,b,x); t[k]=(t[k<<1]+t[k<<1|1])%P; } inline int Query(int k,int l,int r,int a,int b) { if(a>r || b<l) return 0; if(a>=l && b<=r) return t[k]; Update(k); int mid=(a+b)>>1; return (Query(k<<1,l,r,a,mid)+Query(k<<1|1,l,r,mid+1,b))%P; } int main() { // freopen("input.txt","r",stdin); scanf("%d%d%d%d",&n,&m,&root,&P); for(int i=1;i<=n;i++) scanf("%d",&val[i]); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } dfs1(root,0); dfs2(root,root); while(size<n) size<<=1; Build(1,1,n,1,size); while(m--) { int op,x,y,z,ans=0; scanf("%d",&op); if(op==1) { scanf("%d%d%d",&x,&y,&z); while(top[x]!=top[y]) if(dep[top[x]]>dep[top[y]]) { Modify(1,id[top[x]],id[x],1,size,z); x=fa[top[x]]; } else { Modify(1,id[top[y]],id[y],1,size,z); y=fa[top[y]]; } if(dep[x]>dep[y]) swap(x,y); Modify(1,id[x],id[y],1,size,z); } if(op==2) { scanf("%d%d",&x,&y); while(top[x]!=top[y]) if(dep[top[x]]>dep[top[y]]) { ans=(ans+Query(1,id[top[x]],id[x],1,size))%P; x=fa[top[x]]; } else { ans=(ans+Query(1,id[top[y]],id[y],1,size))%P; y=fa[top[y]]; } if(dep[x]>dep[y]) swap(x,y); ans=(ans+Query(1,id[x],id[y],1,size))%P; printf("%d\n",ans); } if(op==3) { scanf("%d%d",&x,&z); Modify(1,id[x],rid[x],1,size,z); } if(op==4) { scanf("%d",&x); printf("%d\n",Query(1,id[x],rid[x],1,size)); } } return 0; }
（待续）
原文：https://www.cnblogs.com/LiuRunky/p/Tree_Spliting.html
