rt,树剖是隔壁的板子。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define mm(x) memset(x,0,sizeof(x))
const int N=1e5+7;
int n,m,cnt=0,tot=0;
int head[N],rk[N],id[N],w[N];
int size[N],d[N],son[N],f[N],top[N];
struct Edge{
	int to,nxt;
}e[N<<1];
struct tree{
	int s,ld;
}t[N<<2];
void init(){
	cnt=tot=0;
	mm(e),mm(t),mm(head),mm(rk),mm(id),mm(size);
	mm(d),mm(son),mm(son),mm(f),mm(top);
}
void add_edge(int fro,int to){
	e[++cnt].to=to;
	e[cnt].nxt=head[fro];
	head[fro]=cnt; 
}
void dfs1(int x,int fa){
	size[x]=1;
	son[x]=0;
	d[x]=d[fa]+1;
	f[x]=fa;
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(to==fa)continue;
		dfs1(to,x);
		size[x]+=size[to];
		if(size[to]>size[son[x]])son[x]=to;
	}
} 
void dfs2(int x,int topx){
	top[x]=topx;
    id[x]=++tot;
    rk[tot]=w[x];
	if(son[x]!=0)dfs2(son[x],topx);
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(to!=f[x]&&to!=son[x])dfs2(to,to);
	}
} 
void pushup(int rt){
	t[rt].s=t[rt<<1].s+t[rt<<1|1].s;
}
void pushdown(int rt,int ln,int rn){
	if(t[rt].ld){
		t[rt<<1].ld=(t[rt<<1].ld+t[rt].ld);
		t[rt<<1|1].ld=(t[rt<<1|1].ld+t[rt].ld);
		t[rt<<1].s+=t[rt].ld*ln;
//		t[rt<<1].s%=mod;
		t[rt<<1|1].s+=t[rt].ld*rn;
//		t[rt<<1|1].s%=mod;
		t[rt].ld=0;
    }
}
void build(int l,int r,int rt){
	t[rt].ld=0;
	if(l==r){
		t[rt].s=rk[l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R)return t[rt].s;
	if(L>r||R<l)return 0;
	int mid=(l+r)/2;
	pushdown(rt,mid-l+1,r-mid);
	return (query(L,R,l,mid,rt<<1)+query(L,R,mid+1,r,rt<<1|1));
}

void update(int L,int R,int C,int l,int r,int rt){
	if(L<=l&&r<=R){
		t[rt].s+=C*(r-l+1);
//		t[rt].s%=mod;
		t[rt].ld+=C;
//		t[rt].ld%=mod;
		return;
	}
	int mid=(l+r)/2;
	pushdown(rt,mid-l+1,r-mid);
	if(L<=mid)update(L,R,C,l,mid,rt<<1);
	if(R>mid)update(L,R,C,mid+1,r,rt<<1|1);
	pushup(rt);
}

int qrange(int l,int r){
	int res=0;
	while(top[l]!=top[r]){
		if(d[top[l]]<d[top[r]])swap(l,r);
		res=(res+query(id[top[l]],id[l],1,n,1));
		l=f[top[l]];
	}
	if(d[l]<d[r])swap(l,r);
	res=(res+query(id[r],id[l],1,n,1));
	return res;
}
int qson(int u){
	return query(id[u],id[u]+size[u]-1,1,n,1);
}
void updrange(int l,int r,int val){
//	val%=mod;
	while(top[l]!=top[r]){
		if(d[top[l]]<d[top[r]])swap(l,r);
		update(id[top[l]],id[l],val,1,n,1);
		l=f[top[l]];
	}
	if(d[l]<d[r])swap(l,r);
	update(id[r],id[l],val,1,n,1);
}
void updrange_(int x,int y,int k){
//	k%=mod;
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]])swap(x,y);
		update(id[top[x]],id[x],k,1,n,1);
		x=f[top[x]];
	}
	if(d[x]>d[y])swap(x,y);
	update(id[x],id[y],k,1,n,1);
}
void updson(int u,int val){
	update(id[u],id[u]+size[u]-1,val,1,n,1);
}
signed main(){
	init();
	ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int gg=1;
    cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1,u,v;i<=n-1;i++)cin>>u>>v,add_edge(u,v),add_edge(v,u); 
	dfs1(gg,0),dfs2(gg,gg),build(1,n,1);
    for(int i=1;i<=m;i++){
    	int op,x,y;
    	cin>>op>>x;
    	if(op==1){
    		cin>>y;
    		update(x,x,y,1,n,1);
		}else{
		    if(op==2){
		    	cin>>y;
		    	updson(x,y);
			}else{
				cout<<qrange(x,gg)<<"\n";
			}
		}
	}
}