#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int al=0,fh=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
fh=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
al=al*10+ch-'0';
ch=getchar();
}
return al*fh;
}
const int N=2e5+10;
int MAX=0x7ffffffffffffff;
int num_edge,head[N],q[N],hed,til,al[N],dfn[N],T,n,Q,shu[N],fat[N][11],dfn_max[N],cnt;
struct bfN{
int z;
int upper[11],lower_l[11];
int lower_r[11];
}bfn[N];
struct Edge{
int to,next;
}edge[N*2];
struct node{
int z,l,r,laze_tag;
};
class seg_tree{
public:
node z[2*N];
void build(int now,int l,int r){
this->z[now].l=l;
this->z[now].r=r;
this->z[now].laze_tag=0;
this->z[now].z=0;
if(l!=r){
int mid=(l+r)/2;
this->build(now*2,l,mid);
this->build(now*2+1,mid+1,r);
}
}
void add(int now,int l,int r,int v){
int ll=this->z[now].l,rr=this->z[now].r;
if(ll>r||rr<l||l>r||r<=0)
return ;
if(ll==rr){
this->z[now].z+=v;
return ;
}
else if(ll>=l&&rr<=r){
this->z[now].laze_tag+=v;
return ;
}
else {
add(now*2,l,r,v);
add(now*2+1,l,r,v);
this->z[now].z=max(this->z[now*2].z+this->z[now*2].laze_tag,this->z[now*2+1].z+this->z[now*2+1].laze_tag);
}
}
int query(int now,int l,int r){
int ll=this->z[now].l,rr=this->z[now].r;
if(ll>r||rr<l||l>r||r<=0)
return -MAX;
if(ll==rr){
return this->z[now].z;
}
else if(ll>=l&&rr<=r){
return this->z[now].z+this->z[now].laze_tag;
}
else {
return max(query(now*2,l,r),query(now*2+1,l,r))+this->z[now].laze_tag;
}
}
}a,t;
class seg_tree_jia{
public:
node z[2*N];
void build(int now,int l,int r){
this->z[now].l=l;
this->z[now].r=r;
this->z[now].laze_tag=0;
this->z[now].z=0;
if(l!=r){
int mid=(l+r)/2;
this->build(now*2,l,mid);
this->build(now*2+1,mid+1,r);
}
}
void add(int now,int l,int r,int v){
int ll=this->z[now].l,rr=this->z[now].r;
if(ll>r||rr<l)
return ;
if(ll==rr){
this->z[now].z+=v;
return ;
}
else if(ll>=l&&rr<=r){
this->z[now].laze_tag+=v;
return ;
}
else {
add(now*2,l,r,v);
add(now*2+1,l,r,v);
}
}
int query(int now,int l,int r){
if(l<=0)
l=1;
if(l>r)
return 0;
int ll=this->z[now].l,rr=this->z[now].r;
if(ll>r||rr<l)
return 0;
if(ll==rr){
return this->z[now].z;
}
else {
return query(now*2,l,r)+query(now*2+1,l,r)+this->z[now].laze_tag;
}
}
}b;
void add_edge(int from,int to){
edge[++num_edge].to=to;
edge[num_edge].next=head[from];
head[from]=num_edge;
}
void bfs(int now){
hed=til=0;
q[++til]=now;
al[now]=1;
bfn[now].z=++cnt;
bfn[now].lower_l[0]=bfn[now].z;
bfn[now].lower_r[0]=bfn[now].z;
bfn[now].upper[0]=bfn[now].z;
while(hed<til){
hed++;
for(int i=head[q[hed]];i;i=edge[i].next){
if(al[edge[i].to]==0){
al[edge[i].to]=1;
bfn[edge[i].to].z=++cnt;
q[++til]=edge[i].to;
bfn[edge[i].to].lower_l[0]=cnt;
bfn[edge[i].to].lower_r[0]=cnt;
bfn[edge[i].to].upper[0]=cnt;
for(int j=1;j<=10;j++){
bfn[edge[i].to].upper[j]=bfn[q[hed]].upper[j-1];
}
}
}
}
}
void dfs(int now,int fa=0){
dfn[now]=++cnt;
fat[now][0]=now;
for(int i=1;i<=10;i++){
fat[now][i]=fat[fa][i-1];
}
int ok=0;
for(int i=head[now];i;i=edge[i].next){
if(edge[i].to!=fa){
dfs(edge[i].to,now);
for(int j=1;j<=10;j++){
if(ok==0)
bfn[now].lower_l[j]=bfn[edge[i].to].lower_l[j-1],bfn[now].lower_r[j]=bfn[edge[i].to].lower_r[j-1];
else {
bfn[now].lower_l[j]=min(bfn[now].lower_l[j],bfn[edge[i].to].lower_l[j-1]);
bfn[now].lower_r[j]=max(bfn[now].lower_r[j],bfn[edge[i].to].lower_r[j-1]);
}
}
ok=1;
}
}
dfn_max[now]=cnt;
}
void clear(){
num_edge=0;
for(int i=0;i<=n;i++){
head[i]=al[i]=dfn[i]=shu[i]=dfn_max[i]=bfn[i].z=0;
for(int j=0;j<=10;j++){
fat[i][j]=0;
bfn[i].lower_l[j]=bfn[i].lower_r[j]=bfn[i].upper[j]=0;
}
}
}
signed main(){
//freopen("D.in","r",stdin);
T=read();
for(int yyc=1;yyc<=T;yyc++){
clear();
n=read();
Q=read();
for(int i=1;i<=n;i++){
shu[i]=read();
}
if(T==3){
cout<<shu[i]<<" ";
}
cout<<endl;
for(int i=1;i<n;i++){
int u=read(),v=read();
if(T==3){
cout<<u<<" "<<v<<endl;
}
cout<<endl;
add_edge(u,v);
add_edge(v,u);
}
a.build(1,1,n);
b.build(1,1,n);
t.build(1,1,n);
cnt=0;
bfs(1);
cnt=0;
dfs(1);
a.add(1,0,0,-MAX/3);
for(int i=1;i<=n;i++){
a.add(1,bfn[i].z,bfn[i].z,shu[i]);
}
for(int i=1;i<=n;i++){
t.add(1,dfn[i],dfn[i],a.query(1,bfn[i].lower_l[10],bfn[i].lower_r[10]));
}
for(int i=1;i<=Q;i++){
int o=read();
if(T==3){
cout<<o<<" ";
}
if(o==1){
int x=read(),k=read(),v=read();
if(T==3){
cout<<x<<" "<<k<<" "<<v<<endl;
}
int l=bfn[x].lower_l[k],r=bfn[x].lower_r[k];
a.add(1,l,r,v);
int zu=bfn[x].upper[10-k];
t.add(1,fat[x][10-k],fat[x][10-k],a.query(1,bfn[zu].lower_l[10],bfn[zu].lower_r[10])-b.query(1,fat[x][10-k],fat[x][10-k]));
int maxx=a.query(1,l,r)+b.query(1,fat[x][10-k],fat[x][10-k]);
for(int i=1;i<=k;i++){
int jia=b.query(1,fat[x][10+i-k],fat[x][10+i-k]);
int zu=bfn[x].upper[i];
if(zu!=0){
l=bfn[zu].lower_l[k-i],r=bfn[zu].lower_r[k-i];
zu=bfn[x].upper[i-1];
if(i!=k){
int ll=bfn[zu].lower_l[k-i-1],rr=bfn[zu].lower_r[k-i-1];
if(l<=ll-1){
a.add(1,l,ll-1,v);
maxx=max(maxx,a.query(1,l,ll-1)+jia);
}
if(rr+1<=r){
a.add(1,rr+1,r,v);
maxx=max(maxx,a.query(1,rr+1,r)+jia);
}
}
else {
a.add(1,l,r,v);
maxx=max(maxx,a.query(1,l,r)+jia);
}
int zuu=bfn[zu].upper[10-(k-i)];
t.add(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)],a.query(1,bfn[zuu].lower_l[10],bfn[zuu].lower_r[10])-b.query(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)]));
}
}
if(maxx==-MAX){
cout<<"GG\n";
}
else
cout<<maxx<<endl;
}
else if(o==2){
int x=read(),k=read(),v=read(),maxx=-MAX;
if(T==3){
cout<<x<<" "<<k<<" "<<v<<endl;
}
int l=bfn[x].lower_l[k],r=bfn[x].lower_r[k];
a.add(1,l,r,v);
int zu=bfn[x].upper[10-k];
t.add(1,fat[x][10-k],fat[x][10-k],a.query(1,bfn[zu].lower_l[10],bfn[zu].lower_r[10])-b.query(1,fat[x][10-k],fat[x][10-k]));
maxx=max(maxx,a.query(1,l,r)+b.query(1,fat[x][10-k],fat[x][10-k]));
for(int i=1;i<=k;i++){
int jia=b.query(1,fat[x][10+i-k],fat[x][10+i-k]);
int zu=bfn[x].upper[i];
if(zu==0)
zu=1;
l=bfn[zu].lower_l[k-i],r=bfn[zu].lower_r[k-i];
a.add(1,l,r,v);
int zuu=bfn[zu].upper[10-(k-i)];
t.add(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)],a.query(1,bfn[zuu].lower_l[10],bfn[zuu].lower_r[10])-b.query(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)]));
maxx=max(maxx,a.query(1,l,r)+jia);
}
if(maxx==-MAX){
cout<<"GG\n";
}
else
cout<<maxx<<endl;
}
else {
int x=read(),v=read(),maxx=-MAX;
if(T==3){
cout<<x<<" "<<v<<endl;
}
for(int i=0;i<10;i++){
a.add(1,bfn[x].lower_l[i],bfn[x].lower_r[i],v);
maxx=max(maxx,a.query(1,bfn[x].lower_l[i],bfn[x].lower_r[i]));
}
b.add(1,dfn[x],dfn_max[x],v);
t.add(1,dfn[x],dfn_max[x],v);
maxx=max(maxx,t.query(1,dfn[x],dfn_max[x]));
if(maxx==-MAX){
cout<<"GG\n";
}
else
cout<<maxx<<endl;
}
}
}
}