myx12345's Blog

var t:array[1..500000]of record
                             a,s:int64;
                            end;
    head,vet,next,top,tid,mx,fa,size,a:array[0..200000]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;

function min(x,y:longint):longint;
begin
 if x<y then exit(X);
 exit(y);
end;

procedure dfs1(u:longint);
var e,v:longint;
begin
 size[u]:=1;
 e:=head[u];
 while e<>0 do
 begin
  v:=vet[e];
  if v<>fa[u] then
  begin
   fa[v]:=u;
   dfs1(v);
   size[u]:=size[u]+size[v];
   mx[u]:=max(mx[u],mx[v]);
  end;
  e:=next[e];
 end;
end;

procedure dfs2(u,ance:longint);
var e,v,k:longint;
begin
 inc(time); tid[u]:=time; top[u]:=ance; mx[u]:=time;
 e:=head[u];
 k:=0;
 while e<>0 do
 begin
  v:=vet[e];
  if (v<>fa[u])and(size[v]>size[k]) then k:=v;
  e:=next[e];
 end;
 if k>0 then
 begin
  dfs2(k,ance);
  mx[u]:=max(mx[u],mx[k]);
 end;
 e:=head[u];
 while e<>0 do
 begin
  v:=vet[e];
  if (v<>fa[u])and(v<>k) then
  begin
   dfs2(v,v);
   mx[u]:=max(mx[u],mx[v]);
  end;
  e:=next[e];
 end;
end;

procedure pushdown(l,r,p:longint);
var mid,ls,rs:longint;
begin
 if l=r then exit;
 mid:=(l+r)>>1;
 ls:=p<<1; rs:=ls+1;
 t[ls].a:=t[ls].a+t[p].a;
 t[rs].a:=t[rs].a+t[p].a;
 t[ls].s:=t[ls].s+(mid-l+1)*t[p].a;
 t[rs].s:=t[rs].s+(r-mid)*t[p].a;
 t[p].a:=0;
end;

function query(l,r,x,y,p:longint):int64;
var mid:longint;
begin
 if (l>=x)and(r<=y) then exit(t[p].s);
 pushdown(l,r,p);
 mid:=(l+r)>>1;
 query:=0;
 if x<=mid then query:=query+query(l,mid,x,y,p<<1);
 if y>mid then query:=query+query(mid+1,r,x,y,p<<1+1);
end;

function querys(x:longint):int64;
begin
 querys:=0;
 while top[x]<>1 do
 begin
  querys:=querys+query(1,n,tid[top[x]],tid[x],1);
  x:=fa[top[x]];
 end;
 querys:=querys+query(1,n,1,tid[x],1);
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+1);
  exit;
 end;
 pushdown(l,r,p);
 mid:=(l+r)>>1;
 if x<=mid then update(l,mid,x,y,v,p<<1);
 if y>mid then update(mid+1,r,x,y,v,p<<1+1);
 t[p].s:=t[p<<1].s+t[p<<1+1].s;
end;


begin
 assign(input,'1.in'); reset(input);
 assign(output,'1.out'); rewrite(output);
 read(n,m);
 for i:=1 to n do read(a[i]);
 for i:=1 to n-1 do
 begin
  read(x,y);
  add(x,y);
  add(y,x);
 end;
 dfs1(1);
 dfs2(1,1);
 for i:=1 to n do update(1,n,tid[i],tid[i],a[i],1);

 for i:=1 to m do
 begin
  read(ch);
  case ch of
   1:
   begin
    read(x,y);
    update(1,n,tid[x],tid[x],y,1);
   end;
   2:
   begin
    read(x,y);
    update(1,n,tid[x],mx[x],y,1);
   end;
   3:
   begin
    read(x);
    writeln(querys(x));
   end;
  end;
 end;

 close(input);
 close(output);
end.