#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define ff(i,s,f) for(int i=s;i<f;i++)
#define fb(i,s,f) for(int i=(s)-1;i>=f;i--)
#define ffi(i,s,f) for(int i=s;i<=f;i++)
#define fbi(i,s,f) for(int i=s;i>=f;i--)
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define ub(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

const int maxn=8e4+10;
const int koren=1150;
const int logg=20;

vector<int> g[maxn];
int n,p[maxn],in[maxn],out[maxn],dist[maxn],cp[maxn],subt[maxn],gt=0;
pii euler[maxn];
pii sparse[3*maxn][logg];
int logaritmi[3*maxn];
pair<pii,pii> buckets[maxn/koren+5][maxn];
bool bio[maxn];

inline void dfs1(int cvor,int d=0,int p=-1){
    euler[gt]=mp(d,cvor);
    in[cvor]=gt++;
    dist[cvor]=d;
    for(int i:g[cvor]){
        if(i==p) continue;
        dfs1(i,d+1,cvor);
        euler[gt]=mp(d,cvor);
        out[cvor]=gt++;
    }
}

inline int dfs2(int cvor,int p=-1){
    int ret=1;
    for(int i:g[cvor]){
        if(i==p) continue;
        if(bio[i]) continue;
        ret+=dfs2(i,cvor);
    }
    subt[cvor]=ret;
    return ret;
}

inline int sparseq(int l,int r){
    return min(sparse[r][logaritmi[r-l+1]],sparse[l+(1<<logaritmi[r-l+1])-1][logaritmi[r-l+1]]).yy;
}

inline void buildsparse(){
    ff(j,0,logg){
        ff(i,0,gt){
            if(j==0){
                sparse[i][j]=euler[i];
            }else{
                sparse[i][j]=min(sparse[i][j-1],sparse[max(i-(1<<(j-1)),0)][j-1]);
            }
        }
    }
    int pom=1;
    int lg=0;
    while(pom<3*maxn){
        logaritmi[pom]=lg;
        pom*=2;
        lg++;
    }
    ff(i,2,3*maxn){
        if(logaritmi[i]!=0) continue;
        logaritmi[i]=logaritmi[i-1];
    }
}

inline int lca(int a,int b){
    return sparseq(min(in[a],in[b]),max(in[a],in[b]));
}

inline int path(int a,int b){
    return dist[a]+dist[b]-2*dist[lca(a,b)];
}

inline void centroid(int cvor,int p=-1){
    dfs2(cvor);
    int pp=-1;
    int siz=subt[cvor];
    while(true){
        bool nasao=false;
        for(int i:g[cvor]){
            if(bio[i] || pp==i) continue;
            if(subt[i]>siz/2){
                pp=cvor;
                cvor=i;
                nasao=true;
                break;
            }
        }
        if(!nasao) break;
    }
    cp[cvor]=p;
    bio[cvor]=true;
    for(int i:g[cvor]) if(!bio[i]) centroid(i,cvor);
}

inline void rem(int koji,int cvor){
    int tren=cvor;
    while(tren!=-1){
        buckets[koji][tren]={{-1,-1},{-1,-1}};
        tren=cp[tren];
    }
}

inline pair<pii,pii> uradi(pii a,pii b,pii c){
    pii nz[3]={a,b,c};
    sort(nz,nz+3,greater<pii>() );
    pair<pii,pii> ret;
    ret.xx=nz[0];
    if(nz[0].yy==nz[1].yy) ret.yy=nz[2];
    else ret.yy=nz[1];
    return ret;
}

inline void add(int koji,int cvor){
    int tren=cvor;
    int pp=-1;
    while(tren!=-1){
        pii novi=mp(path(tren,cvor),pp);
        buckets[koji][cvor]=uradi(buckets[koji][cvor].xx,buckets[koji][cvor].yy,novi);
        pp=tren;
        tren=cp[tren];
    }
}

inline void make(int koji){
    ff(i,koren*koji,min((koren+1)*koji,n)) rem(koji,p[i]);
    ff(i,koren*koji,min((koren+1)*koji,n)) add(koji,p[i]);
}

inline int query(int cvor,int koji){
    int ret=0;
    int tren=cvor;
    int pp=-2;
    while(tren!=-1){
        if(buckets[koji][tren].xx.yy==pp && buckets[koji][tren].yy.xx!=-1) ret=max(ret,buckets[koji][tren].yy.xx+path(cvor,tren));
        else if(buckets[koji][tren].xx.xx!=-1) ret=max(ret,buckets[koji][tren].xx.xx+path(cvor,tren));
        pp=tren;
        tren=cp[tren];
    }
    return ret;
}

inline void init(){
    dfs1(1);
    centroid(1);
    buildsparse();
    ff(i,0,(n-1)/koren+1) make(i);
}

inline void solve(){
	cin>>n;
	ff(i,0,n) cin>>p[i];
	ff(i,1,n){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
	}
	init();
	int q;
	cin>>q;
	while(q--){
        int t;
        cin>>t;
        if(t==1){
            int a,b;
            cin>>a>>b;
            a--;b--;
            swap(p[a],p[b]);
            if(a/koren!=b/koren){
                make(a/koren);
                make(b/koren);
            }
        }else{
            int x,l,r;
            cin>>l>>r>>x;
            l--;r--;
            int res=0;
            ffi(i,l/koren,r/koren){
                int bl=i*koren;
                int br=i*koren+koren-1;
                if(l<=bl && br<=r){
                    res=max(res,query(x,i));
                }else{
                    ffi(j,max(l,bl),min(r,br)){
                        if(l<=j && j<=r) res=max(res,path(x,p[j]));
                    }
                }
            }
            cout<<res<<"\n";
        }
	}
}

int main(){
    ios;
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*
5
5 4 1 2 3
1 2
2 3
1 4
2 5
5
2 3 4 5
1 3 5
2 3 4 5
1 2 4
2 3 4 5
*/