type node1=record
go,next:longint;end;
node2=record
l,r,mx,sum:longint;end;
var i,x,y,n,q,tmp,cnt,sz,code:longint;
ch,st:string;
fa:array[..,..] of longint;
v,deep,son,head,pl,belong,vis:array[..] of longint;
e:array[..] of node1;
t:array[..] of node2;
procedure insert(x,y:longint);
begin
inc(cnt);e[cnt].go:=y;e[cnt].next:=head[x];head[x]:=cnt;
inc(cnt);e[cnt].go:=x;e[cnt].next:=head[y];head[y]:=cnt;
end;
procedure dfs1(x:longint);
var i,j:longint;
begin
son[x]:=;vis[x]:=;
for i:= to do
begin
if deep[x]<(<<i) then break;
fa[x,i]:=fa[fa[x,i-],i-];
end;
i:=head[x];
while i<> do
begin
j:=e[i].go;
if vis[j]= then
begin
deep[j]:=deep[x]+;
fa[j,]:=x;
dfs1(j);
inc(son[x],son[j]);
end;
i:=e[i].next;
end;
end;
procedure dfs2(x,chain:longint);
var i,j,k:longint;
begin
k:=;inc(sz);
pl[x]:=sz;belong[x]:=chain;
i:=head[x];
while i<> do
begin
j:=e[i].go;
if (deep[j]>deep[x]) and (son[j]>son[k]) then k:=j;
i:=e[i].next;
end;
if k= then exit;
dfs2(k,chain);
i:=head[x];
while i<> do
begin
j:=e[i].go;
if (deep[j]>deep[x]) and (k<>j) then
dfs2(j,j);
i:=e[i].next;
end;
end;
function lca(x,y:longint):longint;
var i,tmp:longint;
begin
if deep[x]<deep[y] then begin tmp:=x;x:=y;y:=tmp;end;
tmp:=deep[x]-deep[y];
for i:= to do
if (tmp and (<<i)<>) then x:=fa[x,i];
for i:= downto do
if fa[x,i]<>fa[y,i] then
begin
x:=fa[x,i];y:=fa[y,i];
end;
if x=y then exit(x) else exit(fa[x,]);
end;
procedure build(x,y,k:longint);
var mid:longint;
begin
with t[k] do
begin
l:=x;r:=y;
if l=r then exit;
mid:=(l+r)>>;
build(l,mid,k<<);
build(mid+,r,k<<+);
end;
end;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
procedure change(x,y,k:longint);
var mid:longint;
begin
with t[k] do
begin
if l=r then
begin sum:=y;mx:=y;exit;end;
mid:=(l+r)>>;
if x<=mid then change(x,y,k<<)
else change(x,y,k<<+);
sum:=t[k<<].sum+t[k<<+].sum;
mx:=max(t[k<<].mx,t[k<<+].mx);
end;
end;
function getsum(x,y,k:longint):longint;
var mid:longint;
begin
with t[k] do
begin
if (l=x) and (r=y) then exit(sum);
mid:=(l+r)>>;
if x>mid then exit(getsum(x,y,k<<+))
else if y<=mid then exit((getsum(x,y,k<<)))
else exit(getsum(x,mid,k<<)+getsum(mid+,y,k<<+));
end;
end;
function getmx(x,y,k:longint):longint;
var mid:longint;
begin
with t[k] do
begin
if (l=x) and (r=y) then exit(mx);
mid:=(l+r)>>;
if x>mid then exit(getmx(x,y,k<<+))
else if y<=mid then exit(getmx(x,y,k<<))
else exit(max(getmx(x,mid,k<<),getmx(mid+,y,k<<+)));
end;
end;
function solvesum(x,y:longint):longint;
var sum:longint;
begin
sum:=;
while belong[x]<>belong[y] do
begin
inc(sum,getsum(pl[belong[x]],pl[x],));
x:=fa[belong[x],];
end;
inc(sum,getsum(pl[y],pl[x],));
exit(sum);
end;
function solvemx(x,y:longint):longint;
var mx:longint;
begin
mx:=-maxlongint;
while belong[x]<>belong[y] do
begin
mx:=max(mx,getmx(pl[belong[x]],pl[x],));
x:=fa[belong[x],];
end;
mx:=max(mx,getmx(pl[y],pl[x],));
exit(mx);
end;
procedure init;
begin
readln(n);
for i:= to n- do
begin
readln(x,y);insert(x,y);
end;
for i:= to n do read(v[i]);
end;
procedure solve;
begin
build(,n,);
for i:= to n do change(pl[i],v[i],);
readln(q);
for i:= to q do
begin
readln(st);
ch:=copy(st,,pos(' ',st)-);
delete(st,,pos(' ',st));
val(copy(st,,pos(' ',st)-),x,code);
delete(st,,pos(' ',st));
val(st,y,code);
case ch of
'CHANGE':begin
v[x]:=y;
change(pl[x],y,);
end;
'QMAX':begin
tmp:=lca(x,y);
writeln(max(solvemx(x,tmp),solvemx(y,tmp)));
end;
else begin
tmp:=lca(x,y);
writeln(solvesum(x,tmp)+solvesum(y,tmp)-v[tmp]);
end;
end;
end;
end;
begin
init;
dfs1();
dfs2(,);
solve;
end.
作为以后的模版!