这几天跟lxn学了一下树链剖分（当然ljm小儿子是我的主讲老师啦，还是要感谢的），感觉挺简单的，怕忘在此记录一下。
首先，如果不会线段树，先移步去学一下吧……好了现在我们很熟悉线段树，那么故事开始了：
现在有个大佬走过来，命令你“在一棵树上进行路径的修改、求极值、求和”，你乍一听很高兴，上线段树（当然树状数组，SBT，splay都行啦。。。）！但操作起来你会发现，仅凭线段树是不能快速搞定它的。
怎么办呢？一个貌似很高级的算法出现了，定睛一看，竟是树链剖分。（感觉好傻逼啊~~）
所谓树链，就是树上的路径；剖分，就是把路径分为重链和轻链。
什么是重链和轻链呢？假如现在我们定义 son[v] 表示以v为根的子树的节点数，depth[v] 表示v在树中的深度（根节点的深度为1），那么就有一下定义：
定义科普：
重儿子：son[u] 为v的子节点中son值最大的，那么u就是v的重儿子；
轻儿子：v的其他子节点；
重边：点v与其重儿子的连边；
轻边：点v与其轻儿子的连边；
重链：由重边连成的路径；
轻链：轻边。
由此我们若定义 top[v] 表示v所在的链的顶端节点，father[v] 表示v的父亲，heavy_son[v] 表示与v在同一重链上的v的儿子节点（你可以称其为重儿子），id[v] 表示v与其父亲节点的连边（你可以称其为v的父边）在线段树中的位置。只要把这些东西都求出来，就能用log(n) 的时间完成原问题中的操作了。
一棵树如果被剖分了的话，会具有如下性质：
性质一：如果 (v,u) 为轻边，则 son[u] * 2 < son[v] ；
性质二：从根到某一节点的路径上轻链、重链的个数都不大于log(n) 。
其实就是每经过一条轻边，点的个数就至少除以二。假如不理解，还是劝您先记住为好吧。
有了这些定义和锐利的性质，我们就要开始实现算法了：
一、求出father、depth、son、heavy_son、top、id
我们采用两遍dfs 的方式将它们们求出：
dfs_1：把father、depth、son、heavy_son 求出来，这一步很简单，看看代码就能懂啦；
dfs_2：求出top 和id ；
这一步怎么办呢？首先，对于v ，当heavy_son[v] 存在（即v不是叶子结点）时，显然，我们有top[heavy_son[v]] = top[v] 。线段树中，v的重边应当在v 的父边的后面，记做id[ heavy_son[v]] = totw + 1 , totw表示最后加入的一条边在线段树中的位置。此时为了使一条重链上的各边在线段树中连续分布，应当进行dfs_2(heavy_son[v])。其次，对于v 的各个轻儿子u ，显然有top[u] =u，并且id[u] = totw + 1，进行dfs_2 过程。这样就求出了top 和id ；
将树中各边/点（依题而定）的权值在线段树中更新，建链和建线段树的过程就完成咯。
二、修改操作
eg. 将树从u到v节点最短路径上所有节点的权值加上dis；
我想如果不用树链剖分，你可能会先求LCA，现在我们有了树剖，不妨这么办：
记tu = top[u] ，tv = top[v] ，当tu <> tv 时，不妨设depth[tu] >= depth[tv] ，那么就更新 tu 到 u 点的权值，并使 u = father[tu] ，tu = top[u] ；当 tu = tv 时，u与v在同一条重链上，若u与v不是同一点，就更新u到v路径上的点的权值，否则修改完成。重复上述操作，直至修改完成。（具体代码里有）
其他操作（如求极值，求和等）就类似啦！为了各位好理解，这里附上洛谷P3384的一道模板树链剖分代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define hee for(int i=1;i<=n*2;i++) cout<<depth[i]<<' '; cout<<endl using namespace std; const int maxn=500005; typedef long long LL; int cnte,n,m,r,temp; LL mod; int top[maxn],depth[maxn],father[maxn],id[maxn]; int head[maxn],son[maxn],heavy_son[maxn],a[maxn]; int real[maxn]; // real subscipt -> real[id[i]] == i struct Edge{ int to,next; }edge[maxn]; struct Segment_Tree{ LL l,r,sum,tag; }tree[maxn]; inline int getint(void){ int x=0,f=1; char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1; for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f; } inline LL getll(void){ LL x=0,f=1; char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1; for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void add_edge(const int&u,const int&v){ edge[++cnte].next=head[u]; edge[cnte].to=v; head[u]=cnte; } void DFS_1(int now,int fa){ father[now]=fa; depth[now]=depth[father[now]]+1; son[now]=1; for(int i=head[now];i;i=edge[i].next) if(edge[i].to!=fa){ DFS_1(edge[i].to,now); son[now]+=son[edge[i].to]; if(!heavy_son[now]||son[edge[i].to]>son[heavy_son[now]]) heavy_son[now]=edge[i].to; } } void DFS_2(int now,int first){ top[now]=first; id[now]=++temp; real[id[now]]=now; if(!heavy_son[now]) return ; DFS_2(heavy_son[now],first); for(int i=head[now];i;i=edge[i].next) if(edge[i].to!=heavy_son[now]&&edge[i].to!=father[now]) DFS_2(edge[i].to,edge[i].to); } inline void push_up(int now){ tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum; } inline void push_down(int now){ tree[now<<1].tag+=tree[now].tag; tree[now<<1].sum+=tree[now].tag*(tree[now<<1].r-tree[now<<1].l+1); tree[now<<1|1].tag+=tree[now].tag; tree[now<<1|1].sum+=tree[now].tag*(tree[now<<1|1].r-tree[now<<1|1].l+1); tree[now].tag=0; } void build(int now,int l,int r){ tree[now].l=l; tree[now].r=r; if(l==r){ tree[now].sum=a[real[l]]; return ; } int mid=(tree[now].l+tree[now].r)>>1; build(now<<1,l,mid); build(now<<1|1,mid+1,r); push_up(now); } void update(int now,int ll,int rr,LL x){ if(ll<=tree[now].l&&tree[now].r<=rr){ tree[now].tag+=x; tree[now].sum+=x*(tree[now].r-tree[now].l+1); return ; } push_down(now); int mid=(tree[now].l+tree[now].r)>>1; if(rr<=mid) update(now<<1,ll,rr,x); else if(ll>mid) update(now<<1|1,ll,rr,x); else{ update(now<<1,ll,mid,x); update(now<<1|1,mid+1,rr,x); } push_up(now); } LL query_sum(int now,int ll,int rr){ if(ll<=tree[now].l&&tree[now].r<=rr) return tree[now].sum; push_down(now); int mid=(tree[now].l+tree[now].r)>>1; if(rr<=mid) return query_sum(now<<1,ll,rr); else if(ll>mid) return query_sum(now<<1|1,ll,rr); else return query_sum(now<<1,ll,mid)+query_sum(now<<1|1,mid+1,rr); } void change(int u,int v,LL x){ int tu=top[u],tv=top[v]; while(tu!=tv){ if(depth[tu]<depth[tv]){ swap(tu,tv); swap(u,v); } update(1,id[tu],id[u],x); u=father[tu]; tu=top[u]; } if(depth[u]>depth[v]) swap(u,v); update(1,id[u],id[v],x); } int find_sum(int u,int v){ LL sum=0; int tu=top[u],tv=top[v]; while(tu!=tv){ if(depth[tu]<depth[tv]){ swap(tu,tv); swap(u,v); } sum+=query_sum(1,id[tu],id[u]); sum%=mod; u=father[tu]; tu=top[u]; } if(depth[u]>depth[v]) swap(u,v); sum+=query_sum(1,id[u],id[v]); return sum%=mod; } void root_add(int now,LL x){ int begin=id[now]; int end=id[now]+son[now]-1; update(1,begin,end,x); } LL root_sum(int now){ int begin=id[now]; int end=id[now]+son[now]-1; return query_sum(1,begin,end)%mod; } int main(int argc,char const*argv[]){ n=getint(); m=getint(); r=getint(); mod=getll(); for(int i=1;i<=n;i++) a[i]=getint(); for(int i=1;i<=n-1;i++){ int u=getint(),v=getint(); add_edge(u,v); add_edge(v,u); } DFS_1(r,0); DFS_2(r,r); build(1,1,temp); for(int i=0;i<m;i++){ int t=getint(),x,y,z; if(t==1){ x=getint(),y=getint(),z=getint(); change(x,y,z); } else if(t==2){ x=getint(),y=getint(); printf("%lld\n",find_sum(x,y)); } else if(t==3){ x=getint(),y=getint(); root_add(x,y); } else if(t==4){ x=getint(); printf("%lld\n",root_sum(x)); } //hee; } return 0; } 总之树剖就是这么简单啦，还有一些题，如树的统计（洛谷）等模板题，各位自己去刷吧。最后还是要谢谢ljm儿子的亲情讲解，看来还是养个儿用处多啊！