#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
using namespace std;
const int N = 8e4 + 5;
const ll mod = 1e9 + 7;
vector<int> adj[N];
int p[N], q[N], dep[N], ansbf;
void DfsBf(int s, int e, int d, int l, int r) {
    if (l <= q[s] && q[s] <= r) ansbf = max(ansbf, d);
    for (auto u : adj[s]) {
        if (u == e) continue;
        DfsBf(u, s, d + 1, l, r);
    }
}
void Dfs(int s, int e) {
    for (auto u : adj[s]) {
        if (u == e) continue;
        dep[u] = dep[s] + 1;
        Dfs(u, s);
    }
}
int stmin[4 * N], stmax[4 * N];
void Init(int node, int l, int r) {
    if (l == r) {
        stmin[node] = stmax[node] = dep[p[l]];
        return;
    }
    int mid = l + r >> 1;
    Init(2 * node, l, mid);
    Init(2 * node + 1, mid + 1, r);
    stmin[node] = min(stmin[2 * node], stmin[2 * node + 1]);
    stmax[node] = max(stmax[2 * node], stmax[2 * node + 1]);
}
void Set(int node, int l, int r, int pos) {
    if (l == r) {
        stmin[node] = stmax[node] = dep[p[l]];
        return;
    }
    int mid = l + r >> 1;
    if (pos <= mid) Set(2 * node, l, mid, pos);
    else Set(2 * node + 1, mid + 1, r, pos);
    stmin[node] = min(stmin[2 * node], stmin[2 * node + 1]);
    stmax[node] = max(stmax[2 * node], stmax[2 * node + 1]);
}
pair<int, int> Get(int node, int l, int r, int ql, int qr) {
    if (r < ql || qr < l) return {1e5, -1e5};
    if (ql <= l && r <= qr) return {stmin[node], stmax[node]};
    int mid = l + r >> 1;
    pair<int, int> a = Get(2 * node, l, mid, ql, qr);
    pair<int, int> b = Get(2 * node + 1, mid + 1, r, ql, qr);
    a.first = min(a.first, b.first);
    a.second = max(a.second, b.second);
    return a;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        q[p[i]] = i;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int qr;
    cin >> qr;
    if (n <= 4000 && qr <= 4000) {
        while (qr--) {
            int ty;
            cin >> ty;
            if (ty == 1) {
                int a, b;
                cin >> a >> b;
                swap(p[a], p[b]);
                q[p[a]] = a;
                q[p[b]] = b;
            }
            else {
                int l, r, x;
                cin >> l >> r >> x;
                DfsBf(x, 0, 0, l, r);
                cout << ansbf << en;
            }
        }
        return 0;
    }
    int subtask2 = 1;
    int root = 1;
    for (int i = 1; i <= n; i++) {
        subtask2 &= (adj[i].size() <= 2);
        if (adj[i].size() == 1) root = i;
    }
    if (subtask2) {
        Dfs(root, 0);
        Init(1, 1, n);
        while (qr--) {
            int ty;
            cin >> ty;
            if (ty == 1) {
                int a, b;
                cin >> a >> b;
                swap(p[a], p[b]);
                q[p[a]] = a;
                q[p[b]] = b;
                Set(1, 1, n, a);
                Set(1, 1, n, b);
            }
            else {
                int x, l, r;
                cin >> l >> r >> x;
                pair<int, int> ans = Get(1, 1, n, l, r);
                cout << max(abs(dep[x] - ans.first), abs(dep[x] - ans.second)) << en;
            }
        }
        return 0;
    }
    Dfs(1, 0);
    Init(1, 1, n);
    while (qr--) {
        int ty;
        cin >> ty;
        if (ty == 1) {
            int a, b;
            cin >> a >> b;
            swap(p[a], p[b]);
            q[p[a]] = a;
            q[p[b]] = b;
            Set(1, 1, n, a);
            Set(1, 1, n, b);
        }
        else {
            int x, l, r;
            cin >> l >> r >> x;
            pair<int, int> ans = Get(1, 1, n, l, r);
            cout << ans.second << en;
        }
    }
    return 0;

}