树链剖分的基本题

详细介绍在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]
      
       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     end102     else begin103       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   begin113     if l=r then114     begin115       tree[i].sum:=y;116       tree[i].max:=y;117     end118     else begin119       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   begin128     if (x<=l) and (y>=r) then exit(tree[i].max)129     else begin130       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   begin141     if (x<=l) and (y>=r) then exit(tree[i].sum)142     else begin143       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   begin154     asksum:=0;155     f1:=top[x];156     f2:=top[y];157     while f1<>f2 do158     begin159       if d[f1]>=d[f2] then160       begin161         asksum:=asksum+getsum(1,1,n,c[f1],c[x]);162         x:=fa[f1];163       end164       else begin165         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   begin178     t:=-inf;179     f1:=top[x];180     f2:=top[y];181     while f1<>f2 do  //提取182     begin183       if d[f1]>=d[f2] then184       begin185         t:=max(t,getmax(1,1,n,c[f1],c[x]));186         x:=fa[f1];187       end188       else begin189         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 begin201   readln(n);202   for i:=1 to n-1 do203   begin204     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 do214     read(b[c[i]]);215   build(1,1,n);216   readln(m);217   for i:=1 to m do218   begin219     read(ch);220     s:='';221     while ch<>' ' do222     begin223       s:=s+ch;224       read(ch);225     end;226     readln(x,y);227     if s='QMAX' then228       writeln(askmax(x,y))229     else if s='QSUM' then230       writeln(asksum(x,y))231     else if s='CHANGE' then232     begin233       x:=c[x];234       b[x]:=y;235       add(1,1,n);236     end;237   end;238 end.