#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=1300;
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];
pii segt[4*maxn+10];

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 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)];
}

pii spoji(pii a,pii b){
    pair<int,pii> ret={-1,{0,0}};
    ret=max(ret,mp(path(a.xx,a.yy),mp(a.xx,a.yy)));
    ret=max(ret,mp(path(b.xx,b.yy),mp(b.xx,b.yy)));
    ret=max(ret,mp(path(a.xx,b.yy),mp(a.xx,b.yy)));
    ret=max(ret,mp(path(a.xx,b.xx),mp(a.xx,b.xx)));
    ret=max(ret,mp(path(a.yy,b.xx),mp(a.yy,b.xx)));
    ret=max(ret,mp(path(a.yy,b.yy),mp(a.yy,b.yy)));
    return ret.yy;
}

void build(int ind=1,int l=0,int r=n-1){
    if(l==r){
        segt[ind]=mp(p[l],p[l]);
        return;
    }
    int mid=l+(r-l)/2;
    build(2*ind,l,mid);
    build(2*ind+1,mid+1,r);
    segt[ind]=spoji(segt[2*ind],segt[2*ind+1]);
}

inline int query(int tl,int tr,int cvor,int ind=1,int l=0,int r=n-1){
    if(tl<=l && r<=tr){
        return max(path(cvor,segt[ind].xx),path(cvor,segt[ind].yy));
    }
    int mid=l+(r-l)/2;
    int ret=0;
    if(tl<=mid) ret=max(ret,query(tl,tr,cvor,2*ind,l,mid));
    if(tr>mid) ret=max(ret,query(tl,tr,cvor,2*ind+1,mid+1,r));
    return ret;
}

inline void update(int t,int v,int ind=1,int l=0,int r=n-1){
    if(l==r){
        segt[ind]=mp(v,v);
        return;
    }
    int mid=l+(r-l)/2;
    if(t<=mid) update(t,v,2*ind,l,mid);
    else update(t,v,2*ind+1,mid+1,r);
    segt[ind]=spoji(segt[2*ind],segt[2*ind+1]);
}

inline void init(){
    dfs1(1);
    buildsparse();
    build();
}

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--;
            update(a,p[b]);
            update(b,p[a]);
            swap(p[a],p[b]);
        }else{
            int x,l,r;
            cin>>l>>r>>x;
            l--;r--;
            cout<<query(l,r,x)<<"\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
*/