树剖只能过样例P:( 10pts求调

#include <bits/stdc++.h>
using namespace std;

using namespace std;
typedef long long LL;

const int N=101145;

int first[N],idx;
struct edge{
	int d,ne;
}ed[N*2];
void add_edge(int e,int d)
{
	idx++;
	ed[idx].d=d;
	ed[idx].ne=first[e];
	first[e]=idx;
}

int n,m;
LL a[N];
int dfn[N],tot,top[N],son[N],f[N],sz[N],out[N],dy[N];

void dfs(int now,int fa){
	sz[now]=1;
	f[now]=fa;
	for(int i=first[now];i;i=ed[i].ne){
		int d=ed[i].d;
		if(d==fa) continue;
		dfs(d,now);
		sz[now]+=sz[d];
		if(!son[now]||sz[d]>sz[son[now]]) son[now]=d;
	}
	
}

void dfs2(int now,int last){
	top[now]=last;
	dfn[now]=++tot;
	dy[tot]=now;
	if(son[now]) dfs2(son[now],last);
	for(int i=first[now];i;i=ed[i].ne){
		int d=ed[i].d;
		if(d==son[now]||d==f[now]) continue;
		dfs2(d,d);
	}
	out[now]=tot;
}

struct node{
	LL sum,tag;
	int l,r;
}t[N*4];

void pushdown(node &f,node &l,node &r){
	if(f.tag){
		l.sum+=f.tag*1ll*(l.r-l.l+1);
		l.tag+=f.tag;
		r.sum+=f.tag*1ll*(r.r-r.l+1);
		r.tag+=f.tag;
		f.tag=0;
	}
}

void pushup(int now){
	t[now].sum=t[now<<1].sum+t[now<<1|1].sum;
}

void build(int now,int l,int r){
	t[now].l=l,t[now].r=r;
	if(l==r){
		t[now].sum=a[dy[l]];
		return ;
	}
	int mid=l+r>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	pushup(now);
}

void modify(int now,int L,int R,LL val){
	int l=t[now].l,r=t[now].r;
	if(L<=l&& r<=R){
		t[now].sum+=1ll*(t[now].r-t[now].l+1)*val;
		t[now].tag+=val;
		return ;
	}
	pushdown(t[now],t[now<<1],t[now<<1|1]);
	int mid=l+r>>1;
	if(L<=mid) modify(now<<1,L,R,val);
	if(R>mid) modify(now<<1|1,L,R,val);
	pushup(now);
} 

LL query(int now,int L,int R)
{
	int l=t[now].l,r=t[now].r;
	if(L<=l&&r<=R) return t[now].sum;
	pushdown(t[now],t[now<<1],t[now<<1|1]);
	int mid=l+r>>1;
	LL ans=0;
	if(L<=mid) ans+=query(now<<1,L,R);
	if(R>mid) ans+=query(now<<1|1,L,R);
	return ans;
}

LL modify_tree(int x,LL val){
	int l=dfn[x],r=out[x];
	modify(1,l,r,val);
}

LL modify_point(int x,LL val){
	modify(1,dfn[x],dfn[x],val);
}

LL query_line(int x)
{
	LL ans=0;
	while(top[x]!=1){
		ans+=query(1,dfn[top[x]],dfn[x]);
		x=f[top[x]];
	}
	if(x!=1) ans+=query(1,1,dfn[x]);
	return ans;
}

int main()
{
	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	
	for(int i=1;i<n;i++){
		int aa,bb;
		scanf("%d%d",&aa,&bb);
		add_edge(aa,bb);
		add_edge(bb,aa);
	}
	dfs(1,0);
	dfs2(1,1);
	
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op,x;
		LL aa;
		scanf("%d%d",&op,&x);
		if(op==1) {
			scanf("%lld",&aa);
			modify_point(x,aa);
		}
		if(op==2){
			scanf("%lld",&aa);
			modify_tree(x,aa);
		}
		if(op==3){
			printf("%lld\n",query_line(x));
		}
	}
	
	return 0;
}