题意：
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不
会超过 10^6。
思路：
因为以X为根中的子树分成了一条条重链，而他们的编号是连续的。
所以我们可以在DFS2时找到以x为根时它的子树在线段树中的最大编号mx[x]。
然后就是裸地区间修改和求和。
var t:array[..]of record
a,s:int64;
end;
head,vet,next,top,tid,mx,fa,size,a,son,flag,dep,id:array[..]of longint;
n,m,i,x,y,tot,time,ch:longint; procedure add(a,b:longint);
begin
inc(tot);
next[tot]:=head[a];
vet[tot]:=b;
head[a]:=tot;
end; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; procedure dfs1(u:longint);
var e,maxsize,v:longint;
begin
flag[u]:=; size[u]:=;
e:=head[u]; son[u]:=; maxsize:=;
while e<> do
begin
v:=vet[e];
if flag[v]= then
begin
fa[v]:=u; dep[v]:=dep[u]+;
dfs1(v);
size[u]:=size[u]+size[v];
if size[v]>maxsize then
begin
maxsize:=size[v];
son[u]:=v;
end;
end;
e:=next[e];
end;
end; procedure dfs2(u,ance:longint);
var e,v:longint;
begin
flag[u]:=; inc(time); tid[u]:=time; id[time]:=u; top[u]:=ance;
mx[u]:=time;
if son[u]> then
begin
dfs2(son[u],ance);
mx[u]:=max(mx[u],mx[son[u]]);
end;
e:=head[u];
while e<> do
begin
v:=vet[e];
if flag[v]= then
begin
dfs2(v,v);
mx[u]:=max(mx[u],mx[v]);
end;
e:=next[e];
end;
end; procedure build(l,r,p:longint);
var mid:longint;
begin
if l=r then
begin
t[p].s:=a[id[l]];
exit;
end;
mid:=(l+r)>>;
build(l,mid,p<<);
build(mid+,r,p<<+);
t[p].s:=t[p<<].s+t[p<<+].s;
end; procedure update(l,r,x,y:longint;v:int64;p:longint);
var mid:longint;
begin
if (l>=x)and(r<=y) then
begin
t[p].a:=t[p].a+v;
t[p].s:=t[p].s+v*(r-l+);
exit;
end;
mid:=(l+r)>>;
t[p<<].a:=t[p<<].a+t[p].a;
t[p<<+].a:=t[p<<+].a+t[p].a;
t[p<<].s:=t[p<<].s+(mid-l+)*t[p].a;
t[p<<+].s:=t[p<<+].s+(r-mid)*t[p].a;
t[p].a:=;
if x<=mid then update(l,mid,x,y,v,p<<);
if y>mid then update(mid+,r,x,y,v,p<<+);
t[p].s:=t[p<<].s+t[p<<+].s;
end; function query(l,r,x,y,p:longint):int64;
var mid:longint;
tt:int64;
begin
if (l>=x)and(r<=y) then exit(t[p].s);
mid:=(l+r)>>;
t[p<<].a:=t[p<<].a+t[p].a;
t[p<<+].a:=t[p<<+].a+t[p].a;
t[p<<].s:=t[p<<].s+(mid-l+)*t[p].a;
t[p<<+].s:=t[p<<+].s+(r-mid)*t[p].a;
t[p].a:=;
tt:=;
if x<=mid then tt:=tt+query(l,mid,x,y,p<<);
if y>mid then tt:=tt+query(mid+,r,x,y,p<<+);
exit(tt);
end; function ask(x:longint):int64;
var t:int64;
begin
t:=;
while top[x]<> do
begin
t:=t+query(,n,tid[top[x]],tid[x],);
x:=fa[top[x]];
end;
t:=t+query(,n,,tid[x],);
exit(t);
end; begin
assign(input,'bzoj4034.in'); reset(input);
assign(output,'bzoj4034.out'); rewrite(output);
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();
fillchar(flag,sizeof(flag),);
dfs2(,);
build(,n,); for i:= to m do
begin
read(ch);
case ch of
:
begin
read(x,y);
update(,n,tid[x],tid[x],y,);
end;
:
begin
read(x,y);
update(,n,tid[x],mx[x],y,);
end;
:
begin
read(x);
writeln(ask(x));
end;
end;
end;
close(input);
close(output);
end.