树链剖分是树分解成多条链来解决树上两点之间的路径上的问题
如何求出树链：第一次dfs求出树上每个结点的大小和深度和最大的儿子，第二次dfs就能将最大的儿子串起来并hash（映射）到线段树上（或者其他数据结构上），这就是一条重链。
一些性质：1.在树链上进行的算法要额外乘以一个logn：因为找u，v的lca复杂度为O(logn)，在找lca的过程中进行其它算法操作，所以算总复杂度时要额外乘上logn
2.如果(v,u)为轻边，则siz[u] * 2 < siz[v]
3.从根到某一点的路径上轻链、重链的个数都不大于logn
4.可以沿着重链求出lca 每次求复杂度O(logn)
5.如果出现边权，那就将边权映射到对应的树节点上，根节点是没有被映射的
/* 树链剖分：在一棵树上进行路径的修改，求极值，求和 树链：树上的路径 剖分：把路径分为重链和轻链 siz[v]表示已v为根的子树的节点数，dep[v]表示v的深度(根深度为1) top[v]表示v所在的链的顶端结点，fa[v]表示v的父亲， son[v]表示与v在同一重链上的v的儿子节点(姑且称为重儿子) w[v]表示v与其父亲节点的连边(姑且称为v的父边)在线段树中的位置 重儿子：siz[u]为v的子节点中siz值最大的，那么u就是v的重儿子 轻儿子：v的其它子节点 重边：点v与其重儿子的连边 轻便：点v与其轻儿子的连边 重链：由重边构成的路径 轻链：轻边 性质1：(v,u)为轻边，则siz[u]*2<siz[v] 性质2：从根到某一点的路径上轻链，重链的个数都不大于logn 算法：两个dfs求fa,dep,siz,son,top,w dfs_1:把fa,dep,siz,son求出来 dfs_2:对于v，son[v]存在时(v不是叶子节点)，显然有top[son[v]]==top[v] v的重边应当在v的父边的后面，记w[son[v]]=totw+1 ,totw表示最后加入的一条边在线段树中的位置 此时，为了使一条重链各边在线段树中连续分布，应当进行dfs_2(son[v]); v的各个轻儿子u，显然有top[u]=u,并且w[u]=totw+1,进行dfs_2过程，这就求出了top和w 修改操作：将u到v的路径长得每条边的权值都加上某值x 记 f1=top[u],f2=top[v] 当 f1 != f2 :设dep[f1]>=dep[f2],更新u到f1的父边的权值(logn),并使u=fa[f1] 当 f1 == f2 : u,v在同一条重链上，若u与v不是同一点，就更新u到v路径上的边的权值 否则修改完成 重复上述步骤 spoj375 */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define MAXN 10010 using namespace std; struct Edge{ int to, next; }edge[MAXN*2]; int head[MAXN], tot; int top[MAXN];//所在的重链的顶端结点 int fa[MAXN];//父亲 int deep[MAXN];//深度 int num[MAXN];//子节点数 int p[MAXN];//p[v]表示v与其父亲节点的连边在线段树中的位置 int fp[MAXN];//和p数组相反 int son[MAXN];//重儿子 int pos; void init(){ tot = 0; memset(head, -1, sizeof(head)); pos = 0; memset(son, -1, sizeof(son)); } //链式前向星 void addedge(int u, int v){ edge[tot].to = v; edge[tot].next = head[u];//下一条边存储的下标 head[u] = tot++; } //第一遍求出fa，deep，num，son void dfs1(int u, int pre, int d){ deep[u] = d; fa[u] = pre; num[u] = 1; //遍历u的每个子节点 for(int i = head[u];i != -1; i = edge[i].next){ int v = edge[i].to; if (v != pre){ dfs1(v, u, d+1); num[u]+=num[v]; if (son[u]==-1||num[v]>num[son[u]]) son[u] = v; } } } //第二次dfs求出top和p void getpos(int u, int sp){ top[u] = sp; if (son[u] != -1){//如果不是叶子节点，必有重儿子 p[u] = pos++; //表示u与父亲结点的连边在线段树上的位置 fp[p[u]] = u; getpos(son[u], sp);//顺着重链dfs } else {//叶子节点就不要dfs了 p[u] = pos++; fp[p[u]] = u; return; } for(int i = head[u]; i != -1; i = edge[i].next){//对于各个轻儿子 int v = edge[i].to; if (v != son[u] && v != fa[u]) getpos(v, v); } } //线段树 struct Node{ int l, r; int Max; }segTree[MAXN*3]; void build(int i, int l, int r){ segTree[i].l = l; segTree[i].r = r; segTree[i].Max = 0; if (l==r) return; int mid = l+r >> 1; build(i<<1, l, mid); build(i<<1|1, mid+1, r); } void push_up(int i){ segTree[i].Max = max(segTree[i<<1].Max, segTree[i<<1|1].Max); } void update(int i, int k, int val){//更新线段树的第k个值为val if(segTree[i].l == k && segTree[i].r == k){ segTree[i].Max = val; return; } int mid = segTree[i].l+segTree[i].r >> 1; if (k <= mid) update(i<<1, k, val); else update(i<<1|1, k, val); push_up(i); } //查询线段树中[l,r]的最大值,一条重链上的最大权值是很好查询的 int query(int i, int l, int r){ if(segTree[i].l==l&&segTree[i].r==r) return segTree[i].Max; int mid = segTree[i].l+segTree[i].r>>1; if (r<=mid) return query(i<<1, l, r); else if (l > mid) return query(i<<1|1, l, r); else return max(query(i<<1, l, mid), query(i<<1|1, mid+1, r)); } //查询u->v边的最大值 int find(int u, int v){ int f1 = top[u], f2 = top[v]; int tmp = 0; while(f1 != f2){//两个点不是在同一重链上 if (deep[f1]<deep[f2]){ swap(f1, f2); swap(u, v); }//默认deep[f1]比较大 //当 f1 != f2 :设dep[f1]>=dep[f2],更新u到f1的父边的权值(logn),并使u=fa[f1] tmp = max(tmp, query(1, p[f1], p[u])); u = fa[f1]; f1 = top[u]; }//最后一定会在同一条重链上 if (u==v) return tmp; if (deep[u]>deep[v]) swap(u, v); return max(tmp, query(1, p[son[u]], p[v])); } int e[MAXN][3]; int main(){ int T; int n; scanf("%d", &T); while(T--){ init(); scanf("%d", &n); for(int i = 0; i < n-1; i++){ scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]); addedge(e[i][0], e[i][1]); addedge(e[i][1], e[i][0]); } dfs1(1,0,0); getpos(1,1); build(1,0,pos-1); for(int i = 0; i < n-1; i++){ if (deep[e[i][0]]>deep[e[i][1]]) swap(e[i][0], e[i][1]); update(1, p[e[i][1]], e[i][2]);//把(u,v)的权值加入线段树 } char op[10]; int u, v; while(scanf("%s", op)==1){ if (op[0]=='D') break; scanf("%d%d", &u, &v); if (op[0]=='Q') cout << find(u, v)<<endl; else update(1, p[e[u-1][1]], v);//修改第u条边，其下标就是u-1 } } return 0; }
简化后的代码
/* 树链剖分： 将每一条重链在线段树上铺开，访问顺序越靠前的链越靠线段树左边 */ #include<bits/stdc++.h> using namespace std; #define maxn 10010 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct Edge{ int to,next; }edge[maxn<<1]; int head[maxn],tot; int top[maxn],fa[maxn],deep[maxn],num[maxn],p[maxn],fp[maxn],son[maxn],pos; int init(){ tot=pos=0; memset(head,-1,sizeof head); memset(son,-1,sizeof son); } void addedge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } void dfs1(int u,int pre,int d){ deep[u]=d;fa[u]=pre;num[u]=1; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==pre) continue; dfs1(v,u,d+1); num[u]+=num[v]; if(son[u]==-1 || num[son[u]]<num[v]) son[u]=v; } } void getpos(int u,int sp){ top[u]=sp;p[u]=pos++;fp[p[u]]=u; if(son[u]==-1) return; else getpos(son[u],sp); for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v!=son[u] && v!=fa[u]) getpos(v,v);//重新开一条重链 } } int Max[maxn<<2]; inline void pushup(int rt){Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);} void build(int l,int r,int rt){ Max[rt]=0; if(l==r) return; int m=l+r>>1; build(lson); build(rson); } void update(int pos,int val,int l,int r,int rt){ if(l==r) {Max[rt]=val;return;} int m=l+r>>1; if(pos<=m) update(pos,val,lson); else update(pos,val,rson); pushup(rt); } int query(int L,int R,int l,int r,int rt){ if(L<=l && R>=r) return Max[rt]; int m=l+r>>1,res=-1; if(L<=m) res=max(res,query(L,R,lson)); if(R>m) res=max(res,query(L,R,rson)); return res; } int find(int u,int v){//查询u->v边上的最大值 int f1=top[u],f2=top[v],tmp=0; while(f1!=f2){ if(deep[f1]<deep[f2]){swap(f1,f2);swap(u,v);} tmp=max(tmp,query(p[f1],p[u],0,pos-1,1)); u=fa[f1];f1=top[u]; } if(u==v) return tmp; if(deep[u]>deep[v]) swap(u,v); return max(tmp,query(p[son[u]],p[v],0,pos-1,1)); } int e[maxn<<1][3];//保存边 int main(){ int T,n; cin >> T; while(T--){ init(); scanf("%d",&n); for(int i=0;i<n-1;i++){ scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]); addedge(e[i][0],e[i][1]);addedge(e[i][1],e[i][0]); } dfs1(1,0,0);getpos(1,1);build(0,pos-1,1); for(int i=0;i<n-1;i++){ if(deep[e[i][0]]>deep[e[i][1]]) swap(e[i][0],e[i][1]); update(p[e[i][1]],e[i][2],0,pos-1,1);//其实是把边权映射到点上,第一条边在线段树上对应的下标是1，根节点对应的虚边在线段树上下标是0，权值也是0 } char op[10]; int u,v; while(scanf("%s",op)==1){ if(op[0]=='D') break; scanf("%d%d",&u,&v); if(op[0]=='Q') printf("%d ",find(u,v)); else update(p[e[u-1][1]],v,0,pos-1,1); } } return 0; }