题目大意

题目描述清楚，不做赘述

解题思路

区修点查，考虑线段树

第一步，把节点按dfs序编号，节点 $i$ 记为 $dfn_{i}$ ，将树拆开

第二步，建线段树

观察修改操作 $:$

$op=1$ $:$ 显然地，将 $dfn_{x}$ 到 $dfn_{x}+siz_{x}-1$ 这一段加 $a$ 即可，线段树区修

$op=2$ $:$ $x$ 子树中每个节点 $y$ 增加值不相等，为 $(dep_{y}-dep_{x}+1)×a=dep_{y}×a-(dep_{x}-1)×a$ 。由于单点查询， $×dep_{y}$ 可以在查询时进行计算，所以将 $a$ 与 $-(dep_{x}-1)×a$ 分别存入线段树，区修

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010
int n,m;
vector<int>G[N];
int a[N];
int tsp,dfn[N],_dfn[N],siz[N];
int dis[N];
int dep[N];
void dfs(int x,int xfa){//拆树
	dfn[x]=++tsp;_dfn[tsp]=x;siz[x]=1;
	dis[x]=dis[xfa]+a[x];
	dep[x]=dep[xfa]+1;
	for(int y:G[x])if(y!=xfa){
		dfs(y,x);
		siz[x]+=siz[y];
	}
}
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define MID ((l+r)>>1)
struct node{
	int l,r,sum1,sum2;//分别为 dep[y] 的系数与常数
	int tag1,tag2;
}tr[N<<2];
void pushdown(int p){
	if(tr[p].tag1){
		tr[lc(p)].tag1+=tr[p].tag1;tr[lc(p)].sum1+=tr[p].tag1;
		tr[rc(p)].tag1+=tr[p].tag1;tr[rc(p)].sum1+=tr[p].tag1;
		tr[p].tag1=0;
	}
	if(tr[p].tag2){
		tr[lc(p)].tag2+=tr[p].tag2;tr[lc(p)].sum2+=tr[p].tag2;
		tr[rc(p)].tag2+=tr[p].tag2;tr[rc(p)].sum2+=tr[p].tag2;
		tr[p].tag2=0;
	}
}
void build(int p,int l,int r){
	if(l==r){
		tr[p]={l,r,dis[_dfn[l]],0,0,0};
		return;
	}
	tr[p]={l,r,0,0,0,0};
	build(lc(p),l,MID);build(rc(p),MID+1,r);
}
void chg(int p,int l,int r,int x,int y){
	if(tr[p].r<l||tr[p].l>r)return;
	if(l<=tr[p].l&&tr[p].r<=r){
		tr[p].sum1+=x;
		tr[p].tag1+=x;
		tr[p].sum2+=y;
		tr[p].tag2+=y;
		return;
	}
	pushdown(p);
	chg(lc(p),l,r,x,y);chg(rc(p),l,r,x,y);
}
int query(int p,int pos){
	if(tr[p].r<pos||tr[p].l>pos)return -1e15;
	if(tr[p].l==tr[p].r){
		return tr[p].sum1+tr[p].sum2*dep[_dfn[tr[p].l]];
	}
	pushdown(p);
	return max(query(lc(p),pos),query(rc(p),pos));
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		G[x].push_back(y);G[y].push_back(x);
	}
	
	dep[0]=dis[0]=0;
	dfs(1,0);
	
	build(1,1,n);
	
	for(int i=1;i<=m;i++){
		int op,x,y;cin>>op>>x;
		if(op==1){
			cin>>y;
			chg(1,dfn[x],dfn[x]+siz[x]-1,y,0);
		}
		else if(op==2){
			cin>>y;
			chg(1,dfn[x],dfn[x]+siz[x]-1,-(dep[x]-1)*y,y);
		}
		else{
			cout<<query(1,dfn[x])<<'\n';
		}
	}
	
	return 0;
}