#pragma comment(linker, "/STACK:102400000,102400000")
#include<stdio.h>
#include<algorithm>
#define N 100005
#define M 200005
using namespace std;
int i,j,k,ans,l,test,s,m,n,tot,id,x,y;
int c[N],dep[N],a[N],b[N],t[N],next[M],to[M],last[N],fa[N],f[N],q[N],si[N];
struct node {
    int s,ss,d;
}tr[N*4];
inline void add(int o,int p) {
    next[++tot]=last[o]; last[o]=tot; to[tot]=p;
}
inline void build() {
    int l=0,r=1; q[1]=1; dep[1]=1;
    while (l<r) {
        int k=q[++l];
        for (int i=last[k];i;i=next[i]) if (fa[k]!=to[i]) fa[q[++r]=to[i]]=k,dep[to[i]]=dep[k]+1;
    }
    for (int i=r;i;i--) si[q[i]]++,si[fa[q[i]]]=max(si[fa[q[i]]],si[q[i]]);
}
inline void dfs(int o,int p) {
    if(!p) p=o; f[o]=p; int gt=0;
    b[o]=++tot; t[tot]=a[o];
    for (int i=last[o];i;i=next[i]) {
        if (to[i]==fa[o]) continue;
        if (si[to[i]]+1==si[o]) {
            gt=to[i]; break;
        }
    }
    if (gt) dfs(gt,p);
    for (int i=last[o];i;i=next[i]) {
        if (to[i]==gt||to[i]==fa[o]) continue;
        dfs(to[i],0);
    }
    c[o]=tot;
}
inline void up(int o) {
    if (tr[o*2].d==tr[o*2+1].d) tr[o].d=tr[o*2].d;
    else tr[o].d=0;
    tr[o].s=tr[o*2].s+tr[o*2+1].s;
    tr[o].ss=tr[o*2].ss+tr[o*2+1].ss;
}
inline void build(int o,int l,int r) {
    if (l==r) {
        tr[o].s=t[l]; tr[o].d=tr[o].ss=0; return ;
    }
    tr[o].s=tr[o].ss=tr[o].d=0;
    int mid=(l+r)>>1; 
    build(o*2,l,mid); build(o*2+1,mid+1,r); up(o);
}
inline void down(int o) {
    if (tr[o*2].d!=tr[o].d) {
        int pp=tr[o*2].s+tr[o*2].ss;
        if (tr[o].d==1)
        tr[o*2].ss=pp,tr[o*2].s=0;
        else tr[o*2].s=pp,tr[o*2].ss=0;
    }
    if (tr[o*2+1].d!=tr[o].d) {
        int pp=tr[o*2+1].s+tr[o*2+1].ss;
        if (tr[o].d==1)
        tr[o*2+1].ss=pp,tr[o*2+1].s=0;
        else tr[o*2+1].s=pp,tr[o*2+1].ss=0;
    }
    tr[o*2].d=tr[o*2+1].d=tr[o].d;
}
inline void change(int o,int l,int r,int ll,int rr) {
    if (l==ll&&r==rr) {
        int pp=tr[o].s+tr[o].ss;
        tr[o].ss=pp; tr[o].s=0;
        tr[o].d=1;return ;
    }
    if (tr[o].d) down(o);
    int mid=(l+r)>>1; 
    if (rr<=mid) change(o*2,l,mid,ll,rr);
    else if (ll>mid) change(o*2+1,mid+1,r,ll,rr);
    else {
        change(o*2,l,mid,ll,mid);
        change(o*2+1,mid+1,r,mid+1,rr);
    } up(o);
}
inline void change1(int o,int l,int r,int ll) {
    if (l==ll&&r==ll) {
        int pp=tr[o].s+tr[o].ss;
        tr[o].s=pp; tr[o].ss=0;
        tr[o].d=2;return ;
    }
    if (tr[o].d) down(o);
    int mid=(l+r)>>1; 
    if (ll<=mid) change1(o*2,l,mid,ll);
    else change1(o*2+1,mid+1,r,ll);
    up(o);
}
inline int ask(int o,int l,int r,int ll,int rr,int p) {
    if (l==ll&&r==rr) {
        if (p==1) return tr[o].s;
        else return tr[o].ss;
    }
    if (tr[o].d) down(o); int gt=0;
    int mid=(l+r)>>1;
    if (rr<=mid) gt=ask(o*2,l,mid,ll,rr,p);
    else if (ll>mid) gt=ask(o*2+1,mid+1,r,ll,rr,p);
    else {
        gt=ask(o*2,l,mid,ll,mid,p);
        gt+=ask(o*2+1,mid+1,r,mid+1,rr,p);
    }
    up(o); return gt;
}
inline int gett(int o) {
    ans+=ask(1,1,n,b[f[o]],b[o],1);
    change(1,1,n,b[f[o]],b[o]);
    return fa[f[o]];
}
inline void ask(int o,int p) {
    while (f[o]!=f[p]) {
        if (dep[f[o]]>dep[f[p]]) o=gett(o);
        else p=gett(p);
    }
    if (dep[o]>dep[p]) swap(o,p);
    ans+=ask(1,1,n,b[o],b[p],1);
    change(1,1,n,b[o],b[p]);
}
inline void ask1(int o) {
    ans-=ask(1,1,n,b[o],b[o],2);
    change1(1,1,n,b[o]);
}
int main() {
    scanf("%d",&test);
    while (test--) {
        tot=ans=0;
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    for (i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    tot=0;
    build(); 
    dfs(1,0); 
    build(1,1,n);
    scanf("%d",&m);
    for (i=1;i<=m;i++) {
        scanf("%d",&id);
        if (id==1) {
            scanf("%d%d",&x,&y);
            ask(x,y);   
        }
        else if (id==2) {
            scanf("%d",&x);
            ask1(x);   
        }
        else {
            scanf("%d",&x);
            ans+=ask(1,1,n,b[x],c[x],1);
            change(1,1,n,b[x],c[x]);
        }
        printf("%d\n",ans);
    }    
    for (i=1;i<=n;i++) si[i]=dep[i]=f[i]=last[i]=fa[i]=0;
}

}