siz[v]表示以v为根的子树的节点数
top[v]表示v所在的重链的顶端节点
fa[v]表示v的父亲
pos[v]表示v的父边标号
mx[v]表示v的子树中边的标号最大的那条边
参考:http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html
题意：
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
第一次写树链剖分。。
#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>using namespace std;typedef long long LL;#define N 100010int id;int fa[N],siz[N],top[N];int head[N],pos[N],mx[N],v[N];LL sum[N<<2],add[N<<2];struct Node{ int to,next;}e[N<<1];int cnt;int n,m;int uu,vv;int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}void link(int x,int y){ e[++cnt]=(Node){y,head[x]}; head[x]=cnt;}void dfs(int x){ siz[x]=1; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa[x]) { fa[e[i].to]=x; dfs(e[i].to); siz[x]+=siz[e[i].to]; mx[x]=max(mx[x],mx[e[i].to]); }}void dfs2(int x,int cha){ top[x]=cha;pos[x]=mx[x]=++id; int k=0; for(int i=head[x];i;i=e[i].next) if(e[i].to!=fa[x]&&siz[e[i].to]>siz[k]) k=e[i].to; if(k) { dfs2(k,cha);mx[x]=max(mx[x],mx[k]); } for(int i=head[x];i;i=e[i].next) if(e[i].to!=fa[x]&&e[i].to!=k) { dfs2(e[i].to,e[i].to); mx[x]=max(mx[x],mx[e[i].to]); }}void pushup(int now){ sum[now]=sum[now<<1]+sum[now<<1|1];}void pushdown(int nowl,int nowr,int now){ if (nowl==nowr) return; int mid=(nowl+nowr)>>1; LL t=add[now]; add[now]=0; add[now<<1]+=t; add[now<<1|1]+=t; sum[now<<1]+=t*(mid-nowl+1); sum[now<<1|1]+=t*(nowr-mid);}void update(int nowl,int nowr,int now,int l,int r,LL d){ if (add[now]) pushdown(nowl,nowr,now); if (nowl==l && nowr==r) { add[now]+=d; sum[now]+=(nowr-nowl+1)*d; return ; } int mid=(nowl+nowr)>>1; if (l<=mid) update(nowl,mid,now<<1,l,min(r,mid),d); if (r>mid) update(mid+1,nowr,now<<1|1,max(l,mid+1),r,d); pushup(now);}LL query(int nowl,int nowr,int now,int l,int r){ if (add[now]) pushdown(nowl,nowr,now); if (nowl==l && nowr==r) return sum[now]; int mid=(nowl+nowr)>>1; LL ans=0; if (l<=mid) ans+=query(nowl,mid,now<<1,l,min(mid,r)); if (r>mid) ans+=query(mid+1,nowr,now<<1|1,max(mid+1,l),r); return ans;}LL query(int x){ LL ans=0; while (top[x]!=1) { ans+=query(1,n,1,pos[top[x]],pos[x]); x=fa[top[x]]; } ans+=query(1,n,1,1,pos[x]); return ans;}int main(){ n=read(),m=read(); for (int i=1;i<=n;i++) v[i]=read(); for (int i=1;i<n;i++) { uu=read(),vv=read(); link(uu,vv); link(vv,uu); } dfs(1); dfs2(1,1); for (int i=1;i<=n;i++) update(1,n,1,pos[i],pos[i],v[i]); int askd,x,a; while (m--) { askd=read(),x=read(); if (askd==1) { a=read(); update(1,n,1,pos[x],pos[x],a); } if (askd==2) { a=read(); update(1,n,1,pos[x],mx[x],a); } if (askd==3) printf("%lld\n",query(x)); } return 0;}原文：http://www.cnblogs.com/yangjiyuan/p/5328498.html