#include <bits/stdc++.h>
#define MAX2N 160000
#define MAXN 80000
#define pii pair<int,int>
using namespace std;

//vector<int> depth();
vector<int> loc(MAXN);
//vector<int> pat(MAX2N);
vector<int> patd(MAX2N);
int p=0;
int n,n2;
int niz[MAXN];
int logg[MAX2N];
int st[MAX2N][18];
int tree1[MAXN*4], tree2[MAXN*4];

vector<list<int> > adj(MAXN);


int dist(int u,int v){
    if(u==v)return 0;
    int R=max(loc[u],loc[v]);
    int L=min(loc[u],loc[v]);
    int j = logg[R - L + 1];
    int mini = min(st[L][j], st[R - (1 << j) + 1][j]);
    return patd[R]+patd[L]-2*mini;
}

void precompst(){
    logg[1] = 0;
    for (int i = 2; i <= MAX2N; i++) //unapred izracunavamo sve logove
        logg[i] = logg[i/2] + 1; 

    for (int i = 0; i < n2; i++)
        st[i][0] = patd[i];

    int k=18;

    for (int j = 1; j <= k; j++)
        for (int i = 0; i + (1 << j) <= n2; i++)
            st[i][j] = min(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);

}

void dfs(int depth,int cur,int pre){
    loc[cur]=p;
    //pat[p]=cur;
    patd[p++]=depth; //patimo dubino a ne koji cvor smo obisli jer nam nije potrebno za LCA
    for(auto x:adj[cur]){
        if(x!=pre)
        {
            dfs(depth+1,x,cur);
            //pat[p]=cur;
            patd[p++]=depth; // Alternativa bi bila da ponovo "stavljamo cvor na putanji kada izlazimo iz cvora, a ne kada se vratimo do cvora"
        }
    }
}

pair<int,int> bestcombo(int l1,int l2,int r1,int r2){
    int m1;
    int m2;

    m1=l1;
    m2=l2;

    if(dist(m1,m2)<dist(l1,r1)){
        m1=l1;
        m2=r1;
    }
    if(dist(m1,m2)<dist(l1,r2)){
        m1=l1;
        m2=r2;
    }
    if(dist(m1,m2)<dist(l2,r1)){
        m1=l2;
        m2=r1;
    }
    if(dist(m1,m2)<dist(l2,r2)){
        m1=l2;
        m2=r2;
    }
    if(dist(m1,m2)<dist(r1,r2)){
        m1=r1;
        m2=r2;
    }
    return {m1,m2};
}

void ctree(int l,int r,int v){
    if(l==r){
        tree1[v]=tree2[v]=niz[l];
        return;
    }
    int m=(l+r)/2;
    ctree(l,m,v*2+1);
    ctree(m+1,r,v*2+2);
    int l1=tree1[v*2+1],l2=tree2[v*2+1],r1=tree1[v*2+2],r2=tree2[v*2+2];
    pii b=bestcombo(l1,l2,r1,r2);
    tree1[v]=b.first;
    tree2[v]=b.second;

}

pii quw(int l,int r,int a,int b,int v){
    if (l == a && r == b) {
        return {tree1[v],tree2[v]};
    }
    int m=(l+r)/2;
    pii x={-1,-1},y={-1,-1};
    if(a<=m)
        x=quw(l,m,a,min(b,m),v*2+1);
    if(b>m)
        y=quw(m+1,r,max(a,m+1),b,v*2+2);

    if(x.first<0||y.first<0)return max(x,y);

    return bestcombo(x.first,x.second,y.first,y.second);
}

void updoot(int l,int r,int t,int x,int v){
    if(l==r){
        tree1[v]=x;
        tree2[v]=x;
        return;
    }
    int m=(l+r)/2;

    if(t<=m)updoot(l,m,t,x,v*2+1);

    else updoot(m+1,r,t,x,v*2+2);

    int l1=tree1[v*2+1],l2=tree2[v*2+1],r1=tree1[v*2+2],r2=tree2[v*2+2];
    pii b=bestcombo(l1,l2,r1,r2);
    tree1[v]=b.first;
    tree2[v]=b.second;

}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    n2=n*2-1;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        niz[i]=x-1;
    }
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        adj[x-1].push_back(y-1); //ulaz, adj lista, indeksirani od 0
        adj[y-1].push_back(x-1);
    }

    dfs(0,0,0); //pravi dfs putanju za sparse tabelu -> LCA
    precompst(); //Pravljenje sparse tabelu
    ctree(0,n-1,0);
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int op;
        cin>>op;
        if(op==2){
            int a,b,x;
            cin>>a>>b>>x;
            pii oi=quw(0,n-1,a-1,b-1,0);
            //dist(8,5);
            cout << max(dist(oi.first,x-1),dist(oi.second,x-1)) << endl;
        }
        else{
            int a, b;
            cin>> a >> b;

            updoot(0,n-1,--a,niz[--b],0);
            updoot(0,n-1,b,niz[a],0);
            swap(niz[a],niz[b]);
        }
    }
    return 0;
}