树链剖分的基本题
详细介绍在http://blog.sina.com.cn/s/blog_7a1746820100wp67.html
通过树链剖分我们就可以在树上做线段树操作，完成解答
1 const inf=2147483647; 2 type node=record 3 po,next:longint; 4 end; 5 point=record 6 max,sum:longint; 7 end; 8 9 10 var tree:array[0..120010] of point; 11 size,d,fa,p,b,c,top:array[0..30010] of longint; 12 w:array[0..80010] of node; 13 len,i,n,m,x,y,t:longint; 14 ch:char; 15 s:string; 16 17 function max(a,b:longint):longint; 18 begin 19 if a>b then exit(a) else exit(b); 20 end; 21 22 procedure update(i:longint); 23 begin 24 tree[i].sum:=tree[i*2].sum+tree[i*2+1].sum; 25 tree[i].max:=max(tree[i*2].max,tree[i*2+1].max); 26 end; 27 28 procedure swap(var a,b:longint); 29 var c:longint; 30 begin 31 c:=a; 32 a:=b; 33 b:=c; 34 end; 35 36 procedure add(x,y:longint); 37 begin 38 inc(len); 39 w[len].po:=y; 40 w[len].next:=p[x]; 41 p[x]:=len; 42 end; 43 44 procedure dfs1(x:longint); //预处理 45 var i,y:longint; 46 begin 47 i:=p[x]; 48 size[x]:=1; 49 while i<>0 do 50 begin 51 y:=w[i].po; 52 if fa[x]<>y then 53 begin 54 fa[y]:=x; 55 d[y]:=d[x]+1; 56 dfs1(y); 57 size[x]:=size[x]+size[y]; 58 end; 59 i:=w[i].next; 60 end; 61 end; 62 63 procedure dfs2(x:longint); 64 var i,y,q:longint; 65 begin 66 i:=p[x]; 67 inc(t); 68 c[x]:=t; 69 q:=0; 70 while i<>0 do 71 begin 72 y:=w[i].po; 73 if (c[y]=0) and (size[q]<size[y]) then q:=y; 74 i:=w[i].next; 75 end; 76 if q<>0 then 77 begin 78 top[q]:=top[x]; //重儿子先访问 79 dfs2(q); 80 end; 81 i:=p[x]; //然后访问轻儿子 82 while i<>0 do 83 begin 84 y:=w[i].po; 85 if c[y]=0 then 86 begin 87 top[y]:=y; 88 dfs2(y); 89 end; 90 i:=w[i].next; 91 end; 92 end; 93 94 procedure build(i,l,r:longint); 95 var m:longint; 96 begin 97 if l=r then 98 begin 99 tree[i].sum:=b[l]; 100 tree[i].max:=b[l]; 101 end 102 else begin 103 m:=(l+r) shr 1; 104 build(i*2,l,m); 105 build(i*2+1,m+1,r); 106 update(i); 107 end; 108 end; 109 110 procedure add(i,l,r:longint); 111 var m:longint; 112 begin 113 if l=r then 114 begin 115 tree[i].sum:=y; 116 tree[i].max:=y; 117 end 118 else begin 119 m:=(l+r) shr 1; 120 if x<=m then add(i*2,l,m) else add(i*2+1,m+1,r); 121 update(i); 122 end; 123 end; 124 125 function getmax(i,l,r,x,y:longint):longint; 126 var m,t:longint; 127 begin 128 if (x<=l) and (y>=r) then exit(tree[i].max) 129 else begin 130 m:=(l+r) shr 1; 131 t:=-inf; 132 if x<=m then t:=max(t,getmax(i*2,l,m,x,y)); 133 if y>m then t:=max(t,getmax(i*2+1,m+1,r,x,y)); 134 exit(t); 135 end; 136 end; 137 138 function getsum(i,l,r,x,y:longint):longint; 139 var m,t:longint; 140 begin 141 if (x<=l) and (y>=r) then exit(tree[i].sum) 142 else begin 143 m:=(l+r) shr 1; 144 t:=0; 145 if x<=m then t:=t+getsum(i*2,l,m,x,y); 146 if y>m then t:=t+getsum(i*2+1,m+1,r,x,y); 147 exit(t); 148 end; 149 end; 150 151 function asksum(x,y:longint):longint; 152 var f1,f2:longint; 153 begin 154 asksum:=0; 155 f1:=top[x]; 156 f2:=top[y]; 157 while f1<>f2 do 158 begin 159 if d[f1]>=d[f2] then 160 begin 161 asksum:=asksum+getsum(1,1,n,c[f1],c[x]); 162 x:=fa[f1]; 163 end 164 else begin 165 asksum:=asksum+getsum(1,1,n,c[f2],c[y]); 166 y:=fa[f2]; 167 end; 168 f1:=top[x]; 169 f2:=top[y]; 170 end; 171 if c[x]>c[y] then swap(x,y); 172 asksum:=asksum+getsum(1,1,n,c[x],c[y]); 173 end; 174 175 function askmax(x,y:longint):longint; 176 var f1,f2,t:longint; 177 begin 178 t:=-inf; 179 f1:=top[x]; 180 f2:=top[y]; 181 while f1<>f2 do //提取 182 begin 183 if d[f1]>=d[f2] then 184 begin 185 t:=max(t,getmax(1,1,n,c[f1],c[x])); 186 x:=fa[f1]; 187 end 188 else begin 189 t:=max(t,getmax(1,1,n,c[f2],c[y])); 190 y:=fa[f2]; 191 end; 192 f1:=top[x]; 193 f2:=top[y]; 194 end; 195 if c[x]>c[y] then swap(x,y); 196 t:=max(t,getmax(1,1,n,c[x],c[y])); 197 exit(t); 198 end; 199 200 begin 201 readln(n); 202 for i:=1 to n-1 do 203 begin 204 readln(x,y); 205 add(x,y); 206 add(y,x); 207 end; 208 d[1]:=1; 209 dfs1(1); 210 t:=0; 211 top[1]:=1; 212 dfs2(1); 213 for i:=1 to n do 214 read(b[c[i]]); 215 build(1,1,n); 216 readln(m); 217 for i:=1 to m do 218 begin 219 read(ch); 220 s:=''; 221 while ch<>' ' do 222 begin 223 s:=s+ch; 224 read(ch); 225 end; 226 readln(x,y); 227 if s='QMAX' then 228 writeln(askmax(x,y)) 229 else if s='QSUM' then 230 writeln(asksum(x,y)) 231 else if s='CHANGE' then 232 begin 233 x:=c[x]; 234 b[x]:=y; 235 add(1,1,n); 236 end; 237 end; 238 end.