#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;

const int mxN = 80001;
const int mod = 1e9+7;
const int mxlogN = 20;
const int mxK = 10;

vector<int> adj[mxN];
int pos[mxN];
void dfs(int i, int p, int d)
{
    pos[i] = d;
    for(int j : adj[i])
    {
        if(j!=p) dfs(j, i, d+1);
    }
}
int a[mxN];
const ll inf = 1e9;
struct segTree
{
    struct node
    {
        ll mn;
        ll mx;
    };
    int size;
    vector<node> val; /// minimum, sum count
    void build(int n, int i, int Lx, int Rx)
    {
        if(Rx-Lx==1)
        {
            if(Lx<n) val[i] = {pos[a[Lx]], pos[a[Lx]]};
            else val[i] = {inf, -inf};
            return;
        }
        int m = (Rx+Lx)/2;
        build(n, i*2+1, Lx, m);
        build(n, i*2+2, m, Rx);
        val[i].mn = min(val[i*2+1].mn, val[i*2+2].mn);
        val[i].mx = max(val[i*2+1].mx, val[i*2+2].mx);
    }
    void build(int n)
    {
        size = 1;
        while(size < n) size <<= 1;
        val = vector<node>(size << 1);
        build(n, 0, 0, size);
    }
    void set(int pos, int x, int i, int Lx, int Rx)
    {
        if(Rx-Lx==1)
        {
            val[i] = {x,x};
            return;
        }
        int m = (Rx+Lx)/2;
        if(pos < m) set(pos, x, i*2+1, Lx, m);
        else set(pos, x, i*2+2, m, Rx);
        val[i].mn = min(val[i*2+1].mn, val[i*2+2].mn);
        val[i].mx = max(val[i*2+1].mx, val[i*2+2].mx);
    }
    void set(int i, int x)
    {
        set(i, x, 0, 0, size);
    }
    ll mn(int l, int r, int i, int Lx, int Rx)
    {
        if(Rx <= l || Lx >= r) return inf;
        if(Lx >= l && Rx <= r) return val[i].mn;
        int m = (Rx+Lx)/2;
        return min(mn(l,r,i*2+1,Lx,m), mn(l,r,i*2+2,m,Rx));
    }
    ll mn(int l, int r)
    {
        return mn(l, r, 0, 0, size);
    }
    ll mx(int l, int r, int i, int Lx, int Rx)
    {
        if(Rx <= l || Lx >= r) return -inf;
        if(Lx >= l && Rx <= r) return val[i].mx;
        int m = (Rx+Lx)/2;
        return max(mx(l,r,i*2+1,Lx,m), mx(l,r,i*2+2,m,Rx));
    }
    ll mx(int l, int r)
    {
        return mx(l, r, 0, 0, size);
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n; cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    int mxsz = 0;
    for(int i = 1; i < n; i++)
    {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        mxsz = max(mxsz, (int)adj[u].size());
        mxsz = max(mxsz, (int)adj[v].size());
    }
    ll q; cin >> q;
    if(n*q <= 400000000) ///case 1
    {
        while(q--)
        {
            int t, l, r; cin >> t >> l >> r;
            if(t==1)
            {
                swap(a[l-1], a[r-1]);
            }
            else
            {
                int x; cin >> x;
                dfs(x, -1, 0);
                int mx = 0;
                for(int i = l-1; i < r; i++) mx = max(mx, pos[a[i]]);
                cout << mx << "\n";
            }
        }
        return 0;
    }
    else if(mxsz <= 2) ///case 2
    {
        int root = 0;
        for(int i = 1; i <= n; i++) if(adj[i].size()==1) root = i;
        dfs(root, -1, 0); ///pos[node] = index
        segTree tree;
        tree.build(n);
        while(q--)
        {
            int t, l, r; cin >> t >> l >> r;
            if(t==1)
            {
                int al = a[l-1], ar = a[r-1]; ///pos [1, n]
                tree.set(l-1, pos[ar]);
                tree.set(l-1, pos[al]);
                swap(pos[al], pos[ar]);
                swap(a[l-1], a[r-1]);
            }
            else
            {
                int x; cin >> x;
                cout << max(tree.mx(l-1, r)-pos[x], pos[x]-tree.mn(l-1,r)) << "\n";
            }
        }

    }
    else ///case 3
    {
        dfs(1, -1, 0);
        segTree tree;
        tree.build(n);
        while(q--)
        {
            int t, l, r; cin >> t >> l >> r;
            if(t==1)
            {
                int al = a[l-1], ar = a[r-1]; ///pos [1, n]
                tree.set(l-1, pos[ar]);
                tree.set(l-1, pos[al]);
                swap(pos[al], pos[ar]);
                swap(a[l-1], a[r-1]);
            }
            else
            {
                int x; cin >> x;
                cout << tree.mx(l-1, r) << "\n";
            }
        }
    }
    ///case 4 me mrzi iskucati sa sqrt decomp u O(N sqrtN logN)
}