Description
毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数： Change k w：将第k条树枝上毛毛果的个数改变为w个。 Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。 Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问： Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。树”下面，发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数： Change k w：将第k条树枝上毛毛果的个数改变为w个。 Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。 Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问： Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。
这道题可讲之处显然都在线段树上了...
事实证明现在的泪都是当年学线段树时脑子进的水...
program bzoj1984;
const maxn=;maxm=;
var n,i,j,x,y,z,cnt,t:longint;
ch:char;
ter,next,w:array[-..maxm]of longint;
link,deep,size,v,son,pos,belong:array[-..maxn]of longint;
tr:array[-..*maxn]of record l,r,mx,add,c:longint;wait:boolean;end;
fa:array[-..maxn,-..]of longint; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure add(x,y,z:longint);
begin
inc(j);ter[j]:=y;next[j]:=link[x];link[x]:=j;w[j]:=z;
inc(j);ter[j]:=x;next[j]:=link[y];link[y]:=j;w[j]:=z;
end; procedure dfs1(p:longint);
var i,j:longint;
begin
size[p]:=;
for i:= to do
begin
if deep[p]<= << i then break;
fa[p][i]:=fa[fa[p][i-]][i-];
end;
j:=link[p];
while j<> do
begin
if deep[ter[j]]= then
begin
deep[ter[j]]:=deep[p]+;
fa[ter[j]][]:=p;
v[ter[j]]:=w[j];son[(j+) >> ]:=ter[j];
dfs1(ter[j]);
inc(size[p],size[ter[j]]);
end;
j:=next[j];
end;
end; procedure dfs2(p,chain:longint);
var j,k:longint;
begin
inc(cnt);pos[p]:=cnt;belong[p]:=chain;
k:=;
j:=link[p];
while j<> do
begin
if deep[ter[j]]>deep[p] then
if size[ter[j]]>size[k] then k:=ter[j];
j:=next[j];
end;
if k= then exit;
dfs2(k,chain);
j:=link[p];
while j<> do
begin
if deep[ter[j]]>deep[p] then
if k<>ter[j] then dfs2(ter[j],ter[j]);
j:=next[j];
end;
end; procedure build(p,l,r:longint);
var mid:longint;
begin
tr[p].l:=l;tr[p].r:=r;tr[p].mx:=;tr[p].wait:=false;tr[p].add:=;
if l=r then exit;
mid:=(l+r) >> ;
build(p << ,l,mid);
build(p << +,mid+,r);
end; procedure push(p:longint);
begin
if tr[p].l=tr[p].r then exit;
if tr[p].wait then
begin
//与上一题不同，这一题并不存在下面的点在更新之后能比现在更好的情况所以不需要push(p << 1);push(p << 1+1)
//否则会TLE
tr[p << ].add:=;tr[p << +].add:=;
//这两句很关键 因为当儿子节点再往下更新的时候如果add没有清零再往下的点会被赋上不等于tr[p].mx的值
tr[p << ].mx:=tr[p].mx;tr[p << ].wait:=true;
tr[p << +].mx:=tr[p].mx;tr[p << +].wait:=true;
tr[p].wait:=false;
tr[p].mx:=max(tr[p << ].mx,tr[p << +].mx);
end;
if tr[p].add<> then
begin
inc(tr[p << ].mx,tr[p].add);
if not tr[p << ].wait then inc(tr[p << ].add,tr[p].add);
//这个特判很关键也很隐蔽 因为如果tr[p << 1].wait=True的话它往下传的时候应该把tr[p << 1].mx+tr[p].add传递下去
//但是如果把tr[p << 1].add也加上了tr[p].add的话相当于重复相加 就出错了
inc(tr[p << +].mx,tr[p].add);
if not tr[p << +].wait then inc(tr[p << +].add,tr[p].add);
tr[p].add:=;
tr[p].mx:=max(tr[p << ].mx,tr[p << +].mx);
end;
end; procedure insert(p,l,r,ave:longint);
var mid:longint;
begin
push(p);
if (tr[p].l=l)and(tr[p].r=r) then
begin
tr[p].mx:=ave;tr[p].wait:=true;
exit;
end;
mid:=(tr[p].l+tr[p].r) >> ;
if r<=mid then insert(p << ,l,r,ave) else
if l>mid then insert(p << +,l,r,ave) else
begin
insert(p << ,l,mid,ave);
insert(p << +,mid+,r,ave);
end;
tr[p].mx:=max(tr[p << ].mx,tr[p << +].mx);
end; function lca(x,y:longint):longint;
var tem,i:longint;
begin
if deep[x]<deep[y] then
begin
tem:=x;x:=y;y:=tem;
end;
if deep[x]<>deep[y] then
begin
i:=trunc(ln(deep[x]-deep[y])/ln());
while deep[x]>deep[y] do
begin
while (deep[x]-deep[y]>= << i) do x:=fa[x][i];
dec(i);
end;
end;
if x=y then exit(x);
i:=trunc(ln(n)/ln());
while fa[x][]<>fa[y,] do
begin
while fa[x,i]<>fa[y,i] do
begin
x:=fa[x,i];y:=fa[y,i];
end;
dec(i);
end;
exit(fa[x,]);
end; procedure add(p,l,r,ave:longint);
var mid:longint;
begin
push(p);
if (tr[p].l=l)and(tr[p].r=r) then
begin
inc(tr[p].mx,ave);
inc(tr[p].add,ave);
exit;
end;
mid:=(tr[p].l+tr[p].r) >> ;
if r<=mid then add(p << ,l,r,ave) else
if l>mid then add(p << +,l,r,ave) else
begin
add(p << ,l,mid,ave);
add(p << +,mid+,r,ave);
end;
tr[p].mx:=max(tr[p << ].mx,tr[p << +].mx);
end; function query(p,l,r:longint):longint;
var mid:longint;
begin
push(p);
if (tr[p].l=l)and(tr[p].r=r) then exit(tr[p].mx);
mid:=(tr[p].l+tr[p].r) >> ;
if r<=mid then exit(query(p << ,l,r)) else
if l>mid then exit(query(p << +,l,r)) else
exit(max(query(p << ,l,mid),query(p << +,mid+,r)));
end; procedure solve_change(x,y,z:longint);
begin
while belong[x]<>belong[y] do
begin
insert(,pos[belong[x]],pos[x],z);
x:=fa[belong[x]][];
end;
if x<>y then insert(,pos[y]+,pos[x],z);
end; procedure solve_add(x,y,z:longint);
begin
while belong[x]<>belong[y] do
begin
add(,pos[belong[x]],pos[x],z);
x:=fa[belong[x]][];
end;
if x<>y then add(,pos[y]+,pos[x],z);
end; function solve_mx(x,y:longint):longint;
var sum:longint;
begin
sum:=;
while belong[x]<>belong[y] do
begin
sum:=max(sum,query(,pos[belong[x]],pos[x]));
x:=fa[belong[x]][];
end;
if x<>y then sum:=max(sum,query(,pos[y]+,pos[x]));
exit(sum);
end; begin
readln(n);
j:=;
for i:= to n- do
begin
readln(x,y,z);
add(x,y,z);
end;
deep[]:=;dfs1();
cnt:=;dfs2(,);
build(,,n);
for i:= to n do insert(,pos[i],pos[i],v[i]);
read(ch);
while ch<>'S' do
begin
if ch='C' then
begin
read(ch);
if ch='h' then
begin
readln(ch,ch,ch,ch,x,y);
insert(,pos[son[x]],pos[son[x]],y);
end else
begin
readln(ch,ch,ch,x,y,z);
t:=lca(x,y);
solve_change(x,t,z);solve_change(y,t,z);
end;
end else
if ch='A' then
begin
readln(ch,ch,x,y,z);
t:=lca(x,y);
solve_add(x,t,z);solve_add(y,t,z);
end else
begin
readln(ch,ch,x,y);
t:=lca(x,y);
writeln(max(solve_mx(x,t),solve_mx(y,t)));
end;
read(ch);
end;
end.