Given a tree with N ( N<=100000 ) nodes. Each node has a interger value x_i ( |x_i|<=10000 ).
You have to apply Q ( Q<=100000 ) operations:
1. 1 a b : answer the maximum contiguous sum (maybe empty,will always larger than or equal to 0 ) from the path a->b ( inclusive ).
2. 2 a b c : change all value in the path a->b ( inclusive ) to c.
Input
first line consists one interger N.
next line consists N interger x_i.
next N-1 line , each consists two interger u,v , means that node u and node v are connected
next line consists 1 interger Q.
next Q line : 1 a b or 2 a b c .
Output
For each query, output one line the maximum contiguous sum.
Example
Input:
5
-3 -2 1 2 3
1 2
2 3
1 4
4 5
3
1 2 5
2 3 4 2
1 2 5
Output:
5
9
GSS系列最后一道题终于攻破
树链剖分可做，不过代码很长，280行.....
酝酿了这么久终于写了，以前一直不敢做，今天觉得是时候了
又认真看了一遍入门http://blog.sina.com.cn/s/blog_7a1746820100wp67.html
用了一个下午的时间把它AC了，觉得很欣慰，竟然是一次AC，幸福来得太突然.....
const
inf=-maxlongint;
type
node=record
lson,rson,left,right,lmax,rmax,amax,lazy,sum:longint;
end; var
tree:array[..]of node;
first,next,last:array[..]of longint;
son,fa,size,dep,w,top,root,a:array[..]of longint;
flag:array[..]of boolean;
tot,n,num,ll,rr:longint; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; procedure swap(var x,y:longint);
var
t:longint;
begin
t:=x;x:=y;y:=t;
end; procedure insert(x,y:longint);
begin
inc(num);
last[num]:=y;
next[num]:=first[x];
first[x]:=num;
end; procedure dfs1(x,d,f:longint);
var
i,j:longint;
begin
fa[x]:=f;
flag[x]:=true;
dep[x]:=d;
size[x]:=;
i:=first[x];
j:=;
while i<> do
begin
if flag[last[i]]=false then
begin
dfs1(last[i],d+,x);
inc(size[x],size[last[i]]);
if size[last[i]]>size[j] then j:=last[i];
end;
i:=next[i];
end;
son[x]:=j;
end; procedure build(l,r:longint);
var
now,mid:longint;
begin
inc(tot);
now:=tot;
with tree[now] do
begin
left:=l;
right:=r;
lazy:=inf;
end;
if l=r then exit;
mid:=(l+r)>>;
with tree[now] do
begin
lson:=tot+;
build(l,mid);
rson:=tot+;
build(mid+,r);
end;
end; procedure new(x,now:longint);
begin
with tree[now] do
begin
if left<>right then lazy:=x;
sum:=x*(right-left+);
amax:=max(,sum);
lmax:=amax;
rmax:=amax;
end;
end; procedure down(now:longint);
begin
with tree[now] do
begin
new(lazy,lson);
new(lazy,rson);
lazy:=inf;
end;
end; procedure up(now:longint);
begin
with tree[now] do
begin
sum:=tree[lson].sum+tree[rson].sum;
amax:=max(max(tree[lson].amax,tree[rson].amax),tree[lson].rmax+tree[rson].lmax);
lmax:=max(tree[lson].lmax,tree[lson].sum+tree[rson].lmax);
rmax:=max(tree[rson].rmax,tree[rson].sum+tree[lson].rmax);
end;
end; procedure change(x,now:longint);
var
mid:longint;
begin
with tree[now] do
begin
if(ll<=left)and(rr>=right) then
begin
new(x,now);
exit;
end;
if lazy<>inf then down(now);
mid:=(left+right)>>;
if rr>mid then change(x,rson);
if ll<=mid then change(x,lson);
up(now);
end;
end; procedure dfs2(x,t,ww:longint);
var
i:longint;
begin
flag[x]:=false;
top[x]:=t;
w[x]:=ww;
if son[x]= then
begin
root[x]:=tot+;
build(,ww);
ll:=ww;
rr:=ww;
change(a[x],root[x]);
exit;
end;
dfs2(son[x],t,ww+);
root[x]:=root[son[x]];
ll:=ww;
rr:=ww;
change(a[x],root[x]);
i:=first[x];
while i<> do
begin
if flag[last[i]] then dfs2(last[i],last[i],);
i:=next[i];
end;
end; procedure init;
var
i,x,y:longint;
begin
read(n);
for i:= to n do
read(a[i]);
for i:= to n- do
begin
read(x,y);
insert(x,y);
insert(y,x);
end;
dfs1(,,);
dfs2(,,);
end; procedure get(var am,lm,rm,su:longint;now:longint);
var
mid:longint;
begin
with tree[now] do
begin
if lazy<>inf then down(now);
if(ll<=left)and(rr>=right) then
begin
am:=max(max(am,amax),lm+rmax);
lm:=max(lmax,sum+lm);
rm:=max(rm,su+rmax);
su:=su+sum;
exit;
end;
mid:=(left+right)>>;
if rr>mid then get(am,lm,rm,su,rson);
if ll<=mid then get(am,lm,rm,su,lson);
end;
end; procedure work1;
var
x,y,amax1,lmax1,rmax1,sum1,amax2,lmax2,rmax2,sum2:longint;
begin
read(x,y);
amax1:=;
lmax1:=;
rmax1:=;
sum1:=;
amax2:=;
lmax2:=;
rmax2:=;
sum2:=;
if dep[top[x]]<dep[top[y]] then swap(x,y);
while top[x]<>top[y] do
begin
ll:=;
rr:=w[x];
get(amax1,lmax1,rmax1,sum1,root[x]);
x:=fa[top[x]];
if dep[top[x]]<dep[top[y]] then
begin
swap(x,y);
swap(amax1,amax2);
swap(lmax1,lmax2);
swap(rmax1,rmax2);
swap(sum1,sum2);
end;
end;
if dep[x]<dep[y] then
begin
swap(x,y);
swap(amax1,amax2);
swap(lmax1,lmax2);
swap(rmax1,rmax2);
swap(sum1,sum2);
end;
ll:=w[y];
rr:=w[x];
get(amax1,lmax1,rmax1,sum1,root[x]);
writeln(max(max(amax1,amax2),lmax1+lmax2));
end; procedure work2;
var
x,y,z:longint;
begin
read(x,y,z);
if dep[top[x]]<dep[top[y]] then swap(x,y);
while top[x]<>top[y] do
begin
ll:=;
rr:=w[x];
change(z,root[x]);
x:=fa[top[x]];
if dep[top[x]]<dep[top[y]] then swap(x,y);
end;
if dep[x]<dep[y] then swap(x,y);
ll:=w[y];
rr:=w[x];
change(z,root[x]);
end; procedure work;
var
i,q,s:longint;
begin
read(q);
for i:= to q do
begin
read(s);
if s= then work1
else work2;
end;
end; begin
init;
work;
end.