肯定是树链剖分+线段树，关键是怎么维护
绝对值和这个东西显然不能简单的合并标记
因为对于负数，加之后绝对值和是变小的
那我们考虑对负数和非负数数分别维护
下面的问题就是经过操作如果负数变成了正数怎么办
注意每次加的都是正数，这意味着这样的变化最多发生n次，
每个数发生这种变化，我们就用push到底即可，这样最多nlogn的
所以我们只要在维护一个区间最大负数即可
const inf=;
type node=record
po,next:longint;
end;
link=record
s0,s1,mx:int64;
s:longint;
end; var tree:array[..*] of link;
lazy:array[..*] of int64;
e:array[..*] of node;
top,fa,a,b,c,d,p,s:array[..] of longint;
t,i,x,y,ch,z,len,n,m:longint; function max(a,b:int64):int64;
begin
if a>b then exit(a) else exit(b);
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);
e[len].po:=y;
e[len].next:=p[x];
p[x]:=len;
end; procedure dfs1(x:longint);
var i,y:longint;
begin
i:=p[x];
s[x]:=;
while i<> do
begin
y:=e[i].po;
if s[y]= then
begin
fa[y]:=x;
d[y]:=d[x]+;
dfs1(y);
s[x]:=s[x]+s[y];
end;
i:=e[i].next;
end;
end; procedure dfs2(x:longint);
var q,i,y:longint;
begin
inc(t);
c[x]:=t;
b[t]:=x;
i:=p[x];
q:=;
while i<> do
begin
y:=e[i].po;
if c[y]= then
if s[y]>s[q] then q:=y;
i:=e[i].next;
end;
if q<> then
begin
top[q]:=top[x];
dfs2(q);
end;
i:=p[x];
while i<> do
begin
y:=e[i].po;
if c[y]= then
begin
top[y]:=y;
dfs2(y);
end;
i:=e[i].next;
end;
end; procedure update(i:longint);
begin
tree[i].s0:=tree[i*].s0+tree[i*+].s0;
tree[i].s1:=tree[i*].s1+tree[i*+].s1;
tree[i].s:=tree[i*].s+tree[i*+].s;
tree[i].mx:=max(tree[i*].mx,tree[i*+].mx);
end; procedure build(i,l,r:longint);
var m:longint;
begin
if l=r then
begin
if a[b[l]]>= then
begin
tree[i].s0:=a[b[l]];
tree[i].s:=;
tree[i].mx:=-inf;
end
else begin
tree[i].s1:=a[b[l]];
tree[i].mx:=a[b[l]];
end;
end
else begin
m:=(l+r) shr ;
build(i*,l,m);
build(i*+,m+,r);
update(i);
end;
end; procedure modi(i,len:longint; z:int64);
begin
inc(lazy[i],z);
inc(tree[i].mx,z);
inc(tree[i].s0,int64(tree[i].s)*z);
inc(tree[i].s1,int64(len-tree[i].s)*z);
end; procedure push(i,l,r:longint);
var m:longint;
begin
m:=(l+r) shr ;
modi(i*,m-l+,lazy[i]);
modi(i*+,r-m,lazy[i]);
lazy[i]:=;
end; procedure down(i,l,r:longint);
var m:longint;
begin
if l=r then
begin
tree[i].s0:=tree[i].mx;
tree[i].s:=;
tree[i].mx:=-inf;
tree[i].s1:=;
end
else begin
m:=(l+r) shr ;
if lazy[i]<> then push(i,l,r);
if tree[i*].mx>= then down(i*,l,m);
if tree[i*+].mx>= then down(i*+,m+,r);
update(i);
end;
end; procedure ins(i,l,r,x,y:longint);
var m:longint;
begin
if (x<=l) and (y>=r) then
begin
if tree[i].mx+z>= then
begin
inc(lazy[i],z);
inc(tree[i].mx,z);
down(i,l,r);
end
else modi(i,r-l+,z);
end
else begin
if lazy[i]<> then push(i,l,r);
m:=(l+r) shr ;
if x<=m then ins(i*,l,m,x,y);
if y>m then ins(i*+,m+,r,x,y);
update(i);
end;
end; function get(i,l,r,x,y:longint):int64;
var m:longint;
s:int64; begin
if (x<=l) and (y>=r) then exit(tree[i].s0+abs(tree[i].s1))
else begin
if lazy[i]<> then push(i,l,r);
m:=(l+r) shr ;
s:=;
if x<=m then s:=s+get(i*,l,m,x,y);
if y>m then s:=s+get(i*+,m+,r,x,y);
exit(s);
end;
end; procedure work(x,y:longint);
var f1,f2:longint;
begin
f1:=top[x];
f2:=top[y];
while f1<>f2 do
begin
if d[f1]>=d[f2] then
begin
ins(,,n,c[f1],c[x]);
x:=fa[f1];
f1:=top[x];
end
else begin
ins(,,n,c[f2],c[y]);
y:=fa[f2];
f2:=top[y];
end;
end;
if c[x]>c[y] then swap(x,y);
ins(,,n,c[x],c[y]);
end; function ask(x,y:longint):int64;
var f1,f2:longint;
begin
ask:=;
f1:=top[x];
f2:=top[y];
while f1<>f2 do
begin
if d[f1]>=d[f2] then
begin
ask:=ask+get(,,n,c[f1],c[x]);
x:=fa[f1];
f1:=top[x];
end
else begin
ask:=ask+get(,,n,c[f2],c[y]);
y:=fa[f2];
f2:=top[y];
end;
end;
if c[x]>c[y] then swap(x,y);
ask:=ask+get(,,n,c[x],c[y]);
end; begin
readln(n,m);
for i:= to n do
read(a[i]);
for i:= to n- do
begin
readln(x,y);
add(x,y);
add(y,x);
end;
dfs1();
top[]:=;
dfs2();
build(,,n);
for i:= to m do
begin
read(ch,x,y);
if ch= then
begin
readln(z);
work(x,y);
end
else begin
readln;
writeln(ask(x,y));
end;
end;
end.