代码如下，只需要卡一卡常，算法不需要优化

#pragma once 
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")


#include <bits/stdc++.h>
using namespace std;
const long long MAXN=1e6+50;

const long long BUFFER_SIZE=1<<20;
char rb[BUFFER_SIZE],*rp=rb,*rt=rb;
inline char read_char(){
  return rp==rt?(rt=rb+fread(rb,1,BUFFER_SIZE,stdin),rp=rb,*rp++):*rp++;
}
inline long long read_ll(){
	long long x=0;
	char ch=read_char(),flag=0;
	while (ch!='-'&&(ch<'0'||ch>'9')){
		ch=read_char();
	}
	if(ch=='-'){
		flag=1;
		ch=read_char();
	}
	for (x=0;ch>='0'&&ch<='9';ch=read_char()){
		x=x*10+(ch-'0');
	}
	return flag?-x:x;
}

long long N,M;
long long tr[MAXN];
long long A[MAXN];
struct Edge
{
	long long x,y,Next;
}e[MAXN*4];
struct Node
{
	long long In,Out;
}Cow[MAXN];

long long elast[MAXN],Tot=0;


inline void Add_Edge(long long x,long long y)
{
	Tot++;
	e[Tot].x=x;
	e[Tot].y=y;
	e[Tot].Next=elast[x];
	elast[x]=Tot;
}

long long Cnt=0;
long long father[MAXN];


inline void DFS(long long u,long long fa)
{
	Cow[u].In=++Cnt;
	father[u]=fa;
	for(register long long i=elast[u];i;i=e[i].Next)
	{
		long long v=e[i].y;
		if(v!=fa)
		{
			DFS(v,u);
		}
	}
	Cow[u].Out=Cnt;
}



long long SonTree[MAXN];
int main()
{
	N=read_ll();
	M=read_ll();
	for(register long long i=1;i<=N;i++)
	{
		A[i]=read_ll();
	}

	for(register long long i=1;i<N;i++)
	{
		long long x=read_ll(),y=read_ll();
		Add_Edge(x,y);
		Add_Edge(y,x);
	}
	DFS(1ll,0ll);
	while(M--)
	{
		long long op=read_ll(),x,a;
		if(op==1)
		{
			x=read_ll();
			a=read_ll();
			A[x]+=a;
		}
		if(op==2)
		{
			x=read_ll();
			a=read_ll();
			SonTree[x]+=a;
		}
		if(op==3)
		{
			x=read_ll();
			long long ans=0;
			long long ceng=0;
			while(x>0)
			{
				ceng++;
				ans+=A[x]+SonTree[x]*ceng;
				x=father[x];
			}
			printf("%lld\n",ans);
		}
	}
}