#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;

using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;







//Note to self: Check for overflow

const int N=80004;
const int K=20;

int spars[K][2*N],stp[2*N];
int tin[N],dub[N],vr;
graph g(N);

void dfs(int p, int q)
{
    tin[p]=vr++,dub[p]=dub[q]+1,spars[0][tin[p]]=p;
    for (auto it : g[p]) if (it!=q) dfs(it,p),spars[0][vr++]=p;
}

void build()
{
    int tmp=0;
    fff(i,1,vr)
    {
        if (i==(1<<(tmp+1))) tmp++;
        stp[i]=tmp;
    }
    //fff(i,1,vr) cout<<stp[i]<<" "; cout<<endl;

    ff(i,1,K) fff(j,0,vr-(1<<i))
    {
        int L=spars[i-1][j],R=spars[i-1][j+(1<<(i-1))];
        spars[i][j]=(dub[L]<dub[R]?L:R);
    }
}

int Min(int ll, int rr)
{
    int kk=stp[rr-ll+1];
    int L=spars[kk][ll],R=spars[kk][rr-(1<<kk)+1];
    return (dub[L]<dub[R]?L:R);
}

int Lca(int u, int v)
{
    if (tin[u]>tin[v]) swap(u,v);
    return Min(tin[u],tin[v]);
}

int dist(int u, int v)
{
    if (u==0 || v==0) return -1;
    return dub[u]+dub[v]-2*dub[Lca(u,v)];
}

struct node
{
    int a,b,d;
    node operator+ (node X)
    {
        int a1=a,b1=b,d1=d,di;

        di=dist(a,X.a); if (di>d1) a1=a,b1=X.a,d1=di;
        di=dist(a,X.b); if (di>d1) a1=a,b1=X.b,d1=di;
        di=dist(b,X.a); if (di>d1) a1=b,b1=X.a,d1=di;
        di=dist(b,X.b); if (di>d1) a1=b,b1=X.b,d1=di;
        di=dist(X.a,X.b); if (di>d1) a1=X.a,b1=X.b,d1=di;

        return {a1,b1,d1};
    }
} val[271828];
int l[271828],r[271828];
int k=1;

int perm[N];

void Upd(int p)
{
    val[p+k]={perm[p],perm[p],0};
    p=(p+k)/2;
    while (p)
    {
        val[p]=val[2*p]+val[2*p+1];
        p>>=1;
    }
}

node Qry(int p, int ll, int rr)
{
    if (ll>r[p] || rr<l[p]) return val[0];
    if (ll<=l[p] && rr>=r[p]) return val[p];
    return Qry(2*p,ll,rr)+Qry(2*p+1,ll,rr);
}

void ispisi(int n)
{
    cout<<"PERMUTACIJA: ";
    ff(i,0,n) cout<<perm[i]<<" ";
    cout<<endl;

    for (int kk=1;kk<=k;kk*=2)
    {
        ff(i,kk,2*kk) cout<<"("<<val[i].a<<","<<val[i].b<<") ";
        cout<<endl;
    } cout<<endl;
}

int main()
{
    FAST;

    int n; cin>>n;
    ff(i,0,n) cin>>perm[i];
    ff(i,1,n)
    {
        int u,v; cin>>u>>v;
        g[u].pb(v),g[v].pb(u);
    }

    dfs(1,0);
    build();

    while (k<n) k*=2;
    ff(i,0,2*k) val[i]={0,0,-1};
    ff(i,0,k) l[i+k]=i,r[i+k]=i;
    ff(i,0,n) val[i+k]={perm[i],perm[i],0};
    bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
    bff(i,1,k) val[i]=val[2*i]+val[2*i+1];

    //ispisi(n);

    int q; cin>>q;
    while (q--)
    {
        int t,a,b; cin>>t>>a>>b; a--,b--;
        if (t==1) swap(perm[a],perm[b]),Upd(a),Upd(b);//,ispisi(n);
        else
        {
            int x; cin>>x;
            node ans=Qry(1,a,b);
            cout<<max(dist(ans.a,x),dist(ans.b,x))<<"\n"; //cout<<flush;
        }
    }
}

//Note to self: Check for overflow

/*

5
5 2 3 4 1
1 2
2 3
1 4
2 5
1
2 3 4 5

*/