树链剖分的基本题
详细介绍在http://blog.sina.com.cn/s/blog_7a1746820100wp67.html
通过树链剖分我们就可以在树上做线段树操作，完成解答
const inf=;
type node=record
po,next:longint;
end;
point=record
max,sum:longint;
end; var tree:array[..] of point;
size,d,fa,p,b,c,top:array[..] of longint;
w:array[..] of node;
len,i,n,m,x,y,t:longint;
ch:char;
s:string; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure update(i:longint);
begin
tree[i].sum:=tree[i*].sum+tree[i*+].sum;
tree[i].max:=max(tree[i*].max,tree[i*+].max);
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; procedure add(x,y:longint);
begin
inc(len);
w[len].po:=y;
w[len].next:=p[x];
p[x]:=len;
end; procedure dfs1(x:longint); //预处理
var i,y:longint;
begin
i:=p[x];
size[x]:=;
while i<> do
begin
y:=w[i].po;
if fa[x]<>y then
begin
fa[y]:=x;
d[y]:=d[x]+;
dfs1(y);
size[x]:=size[x]+size[y];
end;
i:=w[i].next;
end;
end; procedure dfs2(x:longint);
var i,y,q:longint;
begin
i:=p[x];
inc(t);
c[x]:=t;
q:=;
while i<> do
begin
y:=w[i].po;
if (c[y]=) and (size[q]<size[y]) then q:=y;
i:=w[i].next;
end;
if q<> then
begin
top[q]:=top[x]; //重儿子先访问
dfs2(q);
end;
i:=p[x]; //然后访问轻儿子
while i<> do
begin
y:=w[i].po;
if c[y]= then
begin
top[y]:=y;
dfs2(y);
end;
i:=w[i].next;
end;
end; procedure build(i,l,r:longint);
var m:longint;
begin
if l=r then
begin
tree[i].sum:=b[l];
tree[i].max:=b[l];
end
else begin
m:=(l+r) shr ;
build(i*,l,m);
build(i*+,m+,r);
update(i);
end;
end; procedure add(i,l,r:longint);
var m:longint;
begin
if l=r then
begin
tree[i].sum:=y;
tree[i].max:=y;
end
else begin
m:=(l+r) shr ;
if x<=m then add(i*,l,m) else add(i*+,m+,r);
update(i);
end;
end; function getmax(i,l,r,x,y:longint):longint;
var m,t:longint;
begin
if (x<=l) and (y>=r) then exit(tree[i].max)
else begin
m:=(l+r) shr ;
t:=-inf;
if x<=m then t:=max(t,getmax(i*,l,m,x,y));
if y>m then t:=max(t,getmax(i*+,m+,r,x,y));
exit(t);
end;
end; function getsum(i,l,r,x,y:longint):longint;
var m,t:longint;
begin
if (x<=l) and (y>=r) then exit(tree[i].sum)
else begin
m:=(l+r) shr ;
t:=;
if x<=m then t:=t+getsum(i*,l,m,x,y);
if y>m then t:=t+getsum(i*+,m+,r,x,y);
exit(t);
end;
end; function asksum(x,y:longint):longint;
var f1,f2:longint;
begin
asksum:=;
f1:=top[x];
f2:=top[y];
while f1<>f2 do
begin
if d[f1]>=d[f2] then
begin
asksum:=asksum+getsum(,,n,c[f1],c[x]);
x:=fa[f1];
end
else begin
asksum:=asksum+getsum(,,n,c[f2],c[y]);
y:=fa[f2];
end;
f1:=top[x];
f2:=top[y];
end;
if c[x]>c[y] then swap(x,y);
asksum:=asksum+getsum(,,n,c[x],c[y]);
end; function askmax(x,y:longint):longint;
var f1,f2,t:longint;
begin
t:=-inf;
f1:=top[x];
f2:=top[y];
while f1<>f2 do //提取
begin
if d[f1]>=d[f2] then
begin
t:=max(t,getmax(,,n,c[f1],c[x]));
x:=fa[f1];
end
else begin
t:=max(t,getmax(,,n,c[f2],c[y]));
y:=fa[f2];
end;
f1:=top[x];
f2:=top[y];
end;
if c[x]>c[y] then swap(x,y);
t:=max(t,getmax(,,n,c[x],c[y]));
exit(t);
end; begin
readln(n);
for i:= to n- do
begin
readln(x,y);
add(x,y);
add(y,x);
end;
d[]:=;
dfs1();
t:=;
top[]:=;
dfs2();
for i:= to n do
read(b[c[i]]);
build(,,n);
readln(m);
for i:= to m do
begin
read(ch);
s:='';
while ch<>' ' do
begin
s:=s+ch;
read(ch);
end;
readln(x,y);
if s='QMAX' then
writeln(askmax(x,y))
else if s='QSUM' then
writeln(asksum(x,y))
else if s='CHANGE' then
begin
x:=c[x];
b[x]:=y;
add(,,n);
end;
end;
end.