#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int B=10;
int inp[1<<18],a[1<<18],fa[1<<18];
int rt[1<<18];
vector<int> e[1<<18],g[1<<18];
int to[1<<18],from[1<<18];
int in[1<<18],out[1<<18];
int le[1<<18][11],ri[1<<18][11];
const int N=1<<18;
struct BIT{int tr[1<<18];
pair<int,int> opers[1<<23];
int opsz;
void add(int x,int k,bool lo=1)
{
	if(lo) opers[++opsz]={x,k};
	while(x<N)tr[x]+=k,x+=x&(-x);
}
int find(int x)
{
	int r=0;
	while(x)r+=tr[x],x-=x&(-x);
	return r;
}
void clr()
{
	while(opsz)
	{
		auto [x,y]=opers[opsz--];
		add(x,-y,0);
	}
}
}T;
int n,m;
int arr[1<<18];
struct SGT
{
	int tag[1<<18];
	int f[1<<18];
	void build(int nl,int nr,int x)
	{
		tag[x]=0;
		if(nl==nr){f[x]=arr[nl];return;}
		int mid=(nl+nr)>>1;
		build(nl,mid,x<<1),
		build(mid+1,nr,(x<<1)+1);
		f[x]=max(f[x<<1],f[(x<<1)+1]);
		return ;
	}
	void pd(int x,int ls,int rs)
	{
		tag[ls]+=tag[x],tag[rs]+=tag[x],
		f[ls]+=tag[x],f[rs]+=tag[x];
		tag[x]=0;
	}
	void update(int nl,int nr,int l,int r,int x,int v)
	{
		if(nr<l||r<nl) return ;
		if(l<=nl&&nr<=r){f[x]+=v;tag[x]+=v;return;}
		int mid=(nl+nr)>>1;
		if(tag[x]) pd(x,x<<1,(x<<1)+1);
		update(nl,mid,l,r,x<<1,v);
		update(mid+1,nr,l,r,(x<<1)+1,v);
		f[x]=max(f[x<<1],f[(x<<1)+1]);
		return ;
	}
	void update(int nl,int nr,int t,int x,int v)
	{
		if(nl==nr){f[x]=v;tag[x]=0;return;}
		int mid=(nl+nr)>>1;
		if(tag[x]) pd(x,x<<1,(x<<1)+1);
		if(t<=mid) update(nl,mid,t,x<<1,v);
		else update(mid+1,nr,t,(x<<1)+1,v);
		f[x]=max(f[x<<1],f[(x<<1)+1]);
		return ;
	}
	int query(int nl,int nr,int l,int r,int x)
	{
		if(nr<l||r<nl) return -1e18;
		if(l<=nl&&nr<=r) return f[x];
		int mid=(nl+nr)>>1;
		if(tag[x]) pd(x,x<<1,(x<<1)+1);
		return max(query(nl,mid,l,r,x<<1),
			query(mid+1,nr,l,r,(x<<1)+1));
	}
}Q1,Q2;
int Kevin(int l,int r,int x)
{
	// printf("kevin %lld %lld %lld\n",l,r,x);
	if(l>r) return -1e18;
	int root=rt[l],val=T.find(root);
	// printf("%lld %lld %lld\n",l,r,x);
	Q1.update(1,n,l,r,1,x);
	int ans=Q1.query(1,n,l,r,1);
	if(root==0) return ans;
	int global=Q1.query(1,n,le[root][B],ri[root][B],1);
	Q2.update(1,n,in[root],1,global);
	// for(int i=l; i<=r; ++i) a[i]+=x,ans=max(ans,a[i]+backup[root]);
	return ans+val;
}
int Haitang(int x,int v)
{
	// printf("haitang %lld %lld\n",x,v);
	T.add(in[x],v);
	T.add(out[x]+1,-v);
	Q2.update(1,n,in[x],out[x],1);
	return Q2.query(1,n,in[x],out[x],1);
}
int counter=0;
void dfs(int x)
{
	in[x]=++counter;
	for(int y:e[x]) dfs(y);
	out[x]=counter;
}
void solve()
{
	T.clr();
	n=read(),m=read();
	for(int i=1; i<=n; ++i) inp[i]=read(),
		e[i].clear(),g[i].clear();
	for(int i=1; i<n; ++i)
	{
		int u=read(),v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	queue<pair<int,int>> q;
	q.push({1,0});fa[1]=0;
	int qwq=0;
	while(!q.empty())
	{
		auto [x,awa]=q.front();q.pop();
		from[++qwq]=x,to[x]=qwq,a[qwq]=inp[x];
		for(int y:g[x]) if(y!=awa)
			fa[y]=x,q.push({y,x});
	}
	for(int i=1; i<=n; ++i)
		for(int j:g[i]) if(to[i]<to[j])
			e[to[i]].push_back(to[j]);
	// for(int i=1; i<=n; ++i)
	for(int i=n; i>=1; --i)
	{
		rt[i]=i;
		for(int j=1; j<=B; ++j) rt[i]=fa[rt[i]];
		sort(e[i].begin(),e[i].end());
		le[i][0]=ri[i][0]=i;
		for(int k=1; k<=B; ++k)
			le[i][k]=n+1,ri[i][k]=0;
		for(int j:e[i])
		{
			for(int k=0; k<B; ++k)
				le[i][k+1]=min(le[i][k+1],le[j][k]),
				ri[i][k+1]=max(ri[i][k+1],ri[j][k]);
		}
	}
	dfs(1);
	for(int i=1; i<=n; ++i) arr[i]=a[i];
	Q1.build(1,n,1);
	for(int i=1; i<=n; ++i) arr[i]=-1e18;
	for(int i=1; i<=n; ++i) arr[in[rt[i]]]=max(arr[in[rt[i]]],a[i]);
	Q2.build(1,n,1);
	while(m--)
	{
		int op=read(),x=read(),ans=-1e18;
		if(op==2)
		{
			int d=read(),v=read();
			for(int i=0,layer=d; x&&i<=d; ++i,x=fa[x])
			{
				// printf("%d %d\n",x,layer);
				int l=le[x][layer],r=ri[x][layer];
				// printf("go %lld %lld\n",l,r);
				ans=max(ans,Kevin(l,r,v));
				
				if(layer==0) break;
				--layer;
				l=le[x][layer],r=ri[x][layer];
				ans=max(ans,Kevin(l,r,v));
				// printf("go %lld %lld\n",l,r);
			}
		}
		else if(op==1)
		{
			int d=read(),v=read();
			for(int i=0,y=0,layer=d; x&&i<=d; ++i,y=x,x=fa[x])
			{
				if(y&&layer)
				{
					int l=le[x][layer],r=ri[x][layer];
					int l1=le[y][layer-1],r1=ri[y][layer-1];
					if(r1==0)
					{
						ans=max(ans,Kevin(l,r,v));
					}
					else
					{
						ans=max(ans,Kevin(l,l1-1,v));
						ans=max(ans,Kevin(r1+1,r,v));
					}
				}
				else
				{
					int l=le[x][layer],r=ri[x][layer];
					// printf("go %lld %lld\n",l,r);
					ans=max(ans,Kevin(l,r,v));
				}
				--layer;
			}
		}
		else
		{
			int v=read();
			for(int i=0; i<B; ++i)
			{
				// printf("%d %d\n",x,layer);
				int l=le[x][i],r=ri[x][i];
				// printf("go %lld %lld\n",l,r);
				ans=max(ans,Kevin(l,r,v));
			}
			// Haitang(l,r,v);
			ans=max(ans,Haitang(x,v));
			
		}
		printf("%lld\n",ans);
	}
	return ;
}
signed main()
{
	for(int T=read();T--;)
	{
		solve();
	}
	return 0;
}