如题

#include<iostream>
#include<cstdio>
using namespace std;
const long long N=100010;
long long n,m,num[N],a[N],cnt1,cnt,id[N];
long long head[N*2],nxt[N*2],to[N*2],dep[N];
long long d[N*4],t[N*4],top[N],fa[N],son[N],size[N];
void add_edge(long long x,long long y){
	to[++cnt1]=y;
	nxt[cnt1]=head[x];
	head[x]=cnt1;
}
void pushup(long long p){
	d[p]=d[p*2]+d[p*2+1];
}
void pushdown(long long p,long long l,long long r){
	t[p*2]+=t[p];
	long long mid=(l+r)/2;
	t[p*2+1]+=t[p];
	d[p*2]+=t[p]*(mid-l+1);
	d[p*2+1]+=t[p]*(r-mid);
	t[p]=0;
}
void build(long long p,long long l,long long r){
	if(l==r){
		d[p]=a[l];
		return ;
	}
	long long mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
}
void update(long long p,long long l,long long r,long long ql,long long qr,long long k){
	if(ql<=l&&r<=qr){
		d[p]+=k*(r-l+1);
		t[p]+=k;
		return ; 
	}
	long long mid=(l+r)/2;
	pushdown(p,l,r);
	if(ql<=mid)update(p*2,l,mid,ql,qr,k);
	if(qr>mid)update(p*2+1,mid+1,r,ql,qr,k);
	pushup(p);
} 
long long query(long long p,long long l,long long r,long long ql,long long qr){
	if(ql<=l&&r<=qr){
		return d[p];
	}
	long long mid=(l+r)/2,res=0;
	pushdown(p,l,r);
	if(ql<=mid)res+=query(p*2,l,mid,ql,qr);
	if(qr>mid)res+=query(p*2+1,mid+1,r,ql,qr);
	return res;
}
void cz1(long long x,long long y){
	update(1,1,n,id[x],id[x],y);
}
void cz2(long long x,long long y){
	update(1,1,n,id[x],id[x]+size[x]-1,y);
}
long long cz3(long long x){
	long long res=0;
	while(x){
		res+=query(1,1,n,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	return res;
}
void dfs1(long long x,long long f){
	fa[x]=f;
	size[x]=1;
	dep[x]=dep[f]+1;
	long long maxn=-1;
	for(long long i=head[x];i;i=nxt[i]){
		if(to[i]==f)continue;
		dfs1(to[i],x);
		size[x]+=size[to[i]];
		if(maxn<size[to[i]])maxn=size[to[i]],son[x]=to[i];
	}
}
void dfs2(long long x,long long topx){
	top[x]=topx;
	id[x]=++cnt;
	a[cnt]=num[x];
	if(son[x]==0)return ;
	dfs2(son[x],topx);
	for(long long i=head[x];i;i=nxt[i]){
		if(to[i]==fa[x]||to[i]==son[x])continue;
		dfs2(to[i],to[i]);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",num+i);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add_edge(x,y),add_edge(y,x);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	while(m--){
		int op,x,y;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d",&x,&y);
			cz1(x,y);
		}else if(op==2){
			scanf("%d%d",&x,&y);
			cz2(x,y);
		}else{
			scanf("%d",&x);	
			printf("%lld\n",cz3(x));
		}
	}
}