#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 80000;
const int BLOCK = 250;
const int LOG = 20;

pair <int, int> far[N+5];

int in[N+5], out[N+5];
int depth[N+5];
int spt[LOG+1][4*N+5];
int LG[4*N+5];
int pv[N+5];
int niz[N+5];

int tjm = 0, td = 0;

vector <int> graf[N+5];

bool is_parent(int a, int b){
    return in[a] <= in[b] && out[b] <= out[a];
}

void dfs(int v, int p){
    depth[v] = depth[p] + 1;
    in[v] = ++tjm;
    spt[0][++td] = depth[v];
    pv[v] = td;
    for(auto c : graf[v]) if(c != p) dfs(c, v), spt[0][++td] = depth[v];
    out[v] = ++tjm;
    spt[0][++td] = depth[v];
}

int rmq(int l, int r){
    int j = LG[r - l + 1];
    return min(spt[j][l], spt[j][r - (1 << j) + 1]);
}

int dist(int a, int b){
    if(is_parent(a, b) || is_parent(b, a)) return abs(depth[a] - depth[b]);
    if(pv[a] > pv[b]) swap(a, b);
    return depth[a] + depth[b] - 2*rmq(pv[a], pv[b]);
}

int block[N+5];
int L[N+5], R[N+5];
int d1[N+5], d2[N+5];

void Build(int g){
    int p = L[g], mx = 0;
    for(int i=L[g]; i<=R[g]; i++){
        int x = dist(niz[L[g]], niz[i]);
        if(x > mx) mx = x, p = i;
    }
    int d = p;
    mx = 0;
    for(int i=L[g]; i<=R[g]; i++){
        int x = dist(niz[p], niz[i]);
        if(x > mx) mx = x, d = i;
    }
    d1[g] = p, d2[g] = d;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> niz[i];
    for(int i=2; i<=4*n; i++) LG[i] = LG[i/2] + 1;
    for(int i=1; i<n; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    dfs(1, 0);
    for(int j=1; j<=LOG; j++) for(int i=1; i+(1<<j)-1<=td; i++) spt[j][i] = min(spt[j-1][i], spt[j-1][i + (1 << (j-1))]);
    int qrs;
    cin >> qrs;
    int blocks = 0;
    for(int i=1; i<=n; i++){
        block[i] = 1 + i/BLOCK;
        if(!L[block[i]]) L[block[i]] = i;
        R[block[i]] = max(R[block[i]], i);
        blocks = max(blocks, block[i]);
    }
    for(int i=1; i<=blocks; i++) Build(i);
    while(qrs--){
        int typ;
        cin >> typ;
        if(typ == 1){
            int a, b;
            cin >> a >> b;
            swap(niz[a], niz[b]);
            Build(block[a]);
            Build(block[b]);
        }
        else{
            int tl, tr, x;
            cin >> tl >> tr >> x;
            int mxd = 0;
            for(int g=1; g<=blocks; g++){
                int l = L[g], r = R[g];
                if(tl > r || l > tr) continue;
                else if(tl <= l  && r <= tr){
                    cout << niz[d1[g]] << " ii " << niz[d2[g]] << endl;
                    mxd = max(mxd, dist(niz[d1[g]], x));
                    mxd = max(mxd, dist(niz[d2[g]], x));
                }
                else{
                    for(int i=max(l, tl); i<=min(r, tr); i++) mxd = max(mxd, dist(niz[i], x));
                }
            }
            cout << mxd << "\n";
        }
    }
    return 0;
}

/*
5
2 4 5 3 1
2 1
3 1
4 1
5 2
3
1 3 3
1 5 5
2 1 5 1
*/