【原题】
1036: [ZJOI2008]树的统计Count
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 4465 Solved: 1858
[ Submit ][ Status ]
Description
一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身
Input
输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
Output
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
Sample Input
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
Sample Output
4
1
2
2
10
6
5
6
5
16
HINT
Source
以下内容结合一篇讲的不错的教程，我加了一些改动，更加易懂吧。也请原创大牛释怀 = =。
【问题】 在一棵树上进行路径的修改、求极值、求和。
【树链剖分的概念】 树链，就是树上的路径。剖分，就是把路径分类为 重链 和 轻链 。树链剖分就是把一些点合成一条路径，使其在线段树中的编号（下标）有序，并用线段树来维护，使得查询、修改的效率大大提高（有点像莫队的分块思想）。假设我们把路径分好链了 （先不要在乎是怎么分的），每次询问两个点对（x，y）时，若x和y在同一链中，直接询问线段树中的u和v（因为同一条链中下标是连续的）u，v是x，y对应的线段树中的点。否则的话，我们从深度大的点上一点一点向上爬，每次记录该点所在的链上的情况，直到x，y在同一条链上。
【注意】树链剖分中的线段树中每个点代表的意义可以是原图的边或点。这道题是点，我就以点来叙述。
【数组含义简介】记num[v]表示以v为根的子树的节点数，deep[v]表示v的深度(根深度为1)，top[v]表示v所在的链的顶端节点，f[v]表示v的父亲，son[v]表示与v在同一重链上的v的儿子节点（姑且称为 重儿子 ），tree[v]表示节点v在线段树中的编号，pre[v]表示线段树中编号是v的节点所对应的原图中的点（与tree相反）
只要把这些东西求出来，就能用logn的时间完成原问题中的操作。
【术语解释】
重儿子 ：num[u]为v的子节点中num值最大的，那么u就是v的重儿子。
轻儿子 ：v的其它子节点。
重边 ：点v与其重儿子的连边。
轻边 ：点v与其轻儿子的连边。
重链 ：由重边连成的路径。
轻链： 轻边。
剖分后的树有如下性质：
性质1： 如果(v,u)为轻边，则siz[u] * 2 < siz[v]；
性质2： 从根到某一点的路径上轻链、重链的个数都不大于logn。
至于证明吧，我就不证了~~（其实我不会）只要能应用、并知道复杂度就行了。
【预处理算法实现】
我们可以用两个dfs来求出fa、deep、num、son、top、tree、pre。
dfs_1：把 fa、deep、num、son 求出来，比较简单。
dfs_2：①我们依次标记tree[v]（按搜索的顺序），同时得到pre。
②对于v，当son[v]存在（即v不是叶子节点）时，显然有top[son[v]] = top[v]。（没有就退出）
③然后我们先搜索v的重儿子u，并把u的重儿子、重孙子...的top值也置为top[v]；
④接着我们再搜索v的轻儿子u，并把u的 重儿子、重孙子...的top值置为u；
将树中各边的权值在线段树中更新，建链和建线段树的过程就完成了。
【查询&修改算法实现】
例如将u到v的路径上每条边的权值都加上某值x。
记f1=top[u]，f2=top[v]。
当f1<>f2时：不妨设dep[f1]>=dep[f2]，那么就更新u到f1的权值(logn)，并使u=f[f1]。
当f1=f2时：u与v在同一条重链上，直接更新u到v路径上的点的权值(logn)，修改完成；
重复上述过程，直到修改完成。
如下图所示，较粗的为重边，较细的为轻边。（轻边实质上是长度为1的链）节点编号旁边有个红色点的表明该节点是其所在链的顶端节点。蓝色数字请无视= =（因为是copy人家图的，他的线段树中存的是边）
假设我们要修改11到10的 路径时。
我们通过11和10的不断向上爬（具体操作详见上面），使他们最终在1号点相交。这样，11只经过重链2--11,10只经过自己和链1--14，效率相当的高。（为什么觉得有点像AC自动机呢）
【回归原题】这样，原题就是裸的树链剖分了。具体注释看代码。
1 #include<cstdio> 2 #define S [30005] 3 #define T [120005] 4 #define SS [60005] 5 using namespace std; 6 struct arr{int l,r,sum,max;}a T; //线段树 7 struct adj{int next,go;}adj SS; //边表 8 int tree S,pre S,end S,son S,f S,data S,num S,top S,deep S; 9 int n,i,x,y,cnt,tot,Q; 10 char opt[10]; 11 int Max(int a,int b){return (a>b)?a:b;} 12 void add(int u,int v){adj[++cnt].go=v;adj[cnt].next=end[u];end[u]=cnt;} 13 void dfs1(int k,int fa,int d) //这一段不用解释了吧 14 { 15 deep[k]=d;f[k]=fa;num[k]=1; 16 for (int i=end[k];i;i=adj[i].next) 17 { 18 int go=adj[i].go;if (go==fa) continue; 19 dfs1(go,k,d+1);num[k]+=num[go]; 20 if (!son[k]||num[go]>num[son[k]]) son[k]=go; 21 } 22 } 23 void dfs2(int k,int Number) 24 { 25 top[k]=Number;tree[k]=++tot; //tree[i] 节点i在线段树中的编号 26 pre[tree[k]]=k; //pre[i] 线段树中点为i的对应的节点编号 27 if (!son[k]) return; 28 dfs2(son[k],Number); //先递归重儿子，把他的孩子中的“重”部分也置为Number 29 for (int i=end[k];i;i=adj[i].next) 30 { 31 int go=adj[i].go; 32 if (go!=son[k]&&go!=f[k]) dfs2(go,go); //递归轻儿子 33 } 34 } 35 void build(int k,int l,int r) //这是线段树 36 { 37 a[k].l=l;a[k].r=r; 38 if (l==r) {a[k].sum=a[k].max=data[pre[l]];return;} 39 int mid=(l+r)>>1; 40 build(k<<1,l,mid);build((k<<1)+1,mid+1,r); 41 a[k].sum=a[k<<1].sum+a[(k<<1)+1].sum; 42 a[k].max=Max(a[k<<1].max,a[(k<<1)+1].max); 43 } 44 void update(int k,int x,int jia)//这是线段树 45 { 46 if (a[k].l==a[k].r) 47 { 48 a[k].sum+=jia*(a[k].r-a[k].l+1); 49 a[k].max+=jia;return; 50 } 51 int mid=(a[k].l+a[k].r)>>1; 52 if (x<=mid) update(k<<1,x,jia);else update((k<<1)+1,x,jia); 53 a[k].sum=a[k<<1].sum+a[(k<<1)+1].sum; 54 a[k].max=Max(a[k<<1].max,a[(k<<1)+1].max); 55 } 56 int ask_sum(int k,int x,int y)//这也是线段树 57 { 58 if (a[k].l>=x&&a[k].r<=y) return a[k].sum; 59 int mid=(a[k].l+a[k].r)>>1,o=0; 60 if (x<=mid) o+=ask_sum(k<<1,x,y); 61 if (y>mid) o+=ask_sum((k<<1)+1,x,y); 62 a[k].sum=a[k<<1].sum+a[(k<<1)+1].sum; 63 a[k].max=Max(a[k<<1].max,a[(k<<1)+1].max); 64 return o; 65 } 66 int ask_max(int k,int x,int y)//这也是线段树，稍作改动即可 67 { 68 if (a[k].l>=x&&a[k].r<=y) return a[k].max; 69 int mid=(a[k].l+a[k].r)>>1,o=-1000000000; 70 if (x<=mid) o=ask_max(k<<1,x,y); 71 if (y>mid) o=Max(o,ask_max((k<<1)+1,x,y)); 72 a[k].sum=a[k<<1].sum+a[(k<<1)+1].sum; 73 a[k].max=Max(a[k<<1].max,a[(k<<1)+1].max); 74 return o; 75 } 76 int find_max(int x,int y) 77 { 78 int f1=top[x],f2=top[y],t,ans=-1000000000;//注意ans要置为-INF 79 while (f1!=f2) 80 { 81 if (deep[f1]<deep[f2]) t=f1,f1=f2,f2=t,t=x,x=y,y=t; 82 ans=Max(ans,ask_max(1,tree[f1],tree[x])); 83 x=f[f1];f1=top[x]; 84 } 85 ans=Max(ans,(deep[x]>deep[y])?ask_max(1,tree[y],tree[x]):ask_max(1,tree[x],tree[y])); 86 return ans; 87 } 88 int find_sum(int x,int y) 89 { 90 int f1=top[x],f2=top[y],t,ans=0; 91 while (f1!=f2) 92 { 93 if (deep[f1]<deep[f2]) t=f1,f1=f2,f2=t,t=x,x=y,y=t; 94 ans+=ask_sum(1,tree[f1],tree[x]); 95 x=f[f1];f1=top[x]; 96 } 97 ans+=(deep[x]>deep[y])?ask_sum(1,tree[y],tree[x]):ask_sum(1,tree[x],tree[y]); 98 return ans; 99 } 100 int main() 101 { 102 freopen("count.in","r",stdin); 103 freopen("count.out","w",stdout); 104 scanf("%d",&n); 105 for (i=1;i<n;i++) 106 scanf("%d%d",&x,&y),add(x,y),add(y,x); 107 for (i=1;i<=n;i++) 108 scanf("%d",&data[i]); 109 dfs1(1,0,1);dfs2(1,1); 110 build(1,1,n); 111 scanf("%d",&Q); 112 while (Q) 113 { 114 Q--; 115 scanf("%s%d%d",opt,&x,&y); 116 if (opt[0]==‘C‘) update(1,tree[x],y-data[x]),data[x]=y; 117 else if (opt[1]==‘M‘) printf("%d\n",find_max(x,y)); 118 else printf("%d\n",find_sum(x,y)); 119 } 120 return 0; 121 }
原文：http://www.cnblogs.com/teacherqing/p/6260475.html