#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) __builtin_popcountll(a)
#define bithigh(a) 63-__builtin_clzll(a)
#define lg bithigh
ll highpow(ll a) { return 1LL << (ll)lg(a); }

using namespace std;

const ll LINF = 4e18;
const int mxN = 2e5+10, INF = 2e9, mod = (1 ? 1e9+7 : 998244353);
template<class T>
class segtree{
private:
    int n;
    vector<T> tree, lazy;
    vector<bool> f;
    void init(int n){
        this->n = n;
        if (highpow(n)^n) this->n = 2*highpow(n);
        this->tree = vector<T>(2 * this->n, T());
        this->lazy = vector<T>(2 * this->n, T());
        this->f = vector<bool>(2 * this->n, 0);
    }
    T build(int s, int l, int r, auto* arr){
        if (l == r) return this->tree[s] = T(arr[l]);

        int m = (l + r) / 2;
        T a = build(2*s, l, m, arr);
        T b = build(2*s+1, m+1, r, arr);
        return this->tree[s] = T::op(a, b);
    }
    T update(int s, int l, int r, int ul, int ur, T x){
        eval_lazy(s, l, r);
        if (l > ur || r < ul) return this->tree[s];
        if (l >= ul && r <= ur){
            this->lazy[s].up(x);
            this->f[s] = 1;
            eval_lazy(s, l, r);
            return this->tree[s];
        }

        int m = (l + r) / 2;
        T a = update(2*s, l, m, ul, ur, x);
        T b = update(2*s+1, m+1, r, ul, ur, x);
        return this->tree[s] = T::op(a, b);
    }
    T query(int s, int l, int r, int ql, int qr) {
        eval_lazy(s, l, r);
        if (l > qr || r < ql) return T::null_v();
        if (l >= ql && r <= qr) return this->tree[s];

        int m = (l + r) / 2;
        T a = query(2*s, l, m, ql, qr);
        T b = query(2*s+1, m+1, r, ql, qr);
        return T::op(a, b);
    }
    void eval_lazy(int s, int l, int r){
        if (!this->f[s]) return;
        this->tree[s].lazy_op(this->lazy[s], r-l+1);
        if (l^r){
            this->lazy[2*s].up(this->lazy[s]);
            this->f[2*s] = 1;
            this->lazy[2*s+1].up(this->lazy[s]);
            this->f[2*s+1] = 1;
        }
        this->lazy[s] = T();
        this->f[s] = 0;
    }
public:
    segtree(int n = 0){ init(n); }
    segtree(int n, auto* arr){ init(n); build(1, 0, this->n - 1, arr); }

    void update(int l, int r, auto x) { update(1, 0, this->n-1, l, r, T(x)); }
    auto query(int l, int r) { if (l>r) return T::null_v().val; return query(1, 0, this->n-1, l, r).val; }

    void logTree() const { for (int i = 1; i < 2*this->n; i++) this->tree[i].log(); cerr << endl; }
    void logLazy() const { for (int i = 1; i < 2*this->n; i++) this->lazy[i].log(); cerr << endl; }
};
class max_t{
public:
    ll val;

    max_t(ll val = 0){ this->val = val; }
    static max_t null_v(){ return max_t(-LINF); }

    static max_t op(const max_t& a, const max_t& b){ return max_t(max(a.val, b.val)); }
    // This is currently on set mode but it can be on add.
    max_t up(const max_t& a){ return *this = a; }
    void lazy_op(const max_t& a, int l){ up(a); }

    max_t operator =(const max_t& a){ this->val = a.val; return *this; }
    max_t operator +=(const max_t& a) { this->val += a.val; return *this; }
    max_t operator -=(const max_t& a) { this->val -= a.val; return *this; }
    max_t operator +(const max_t& a) const { return max_t(this->val + a.val); }
    max_t operator -(const max_t& a) const { return max_t(this->val - a.val); }
    bool operator ==(const max_t& a) const { return this->val == a.val; }
    bool operator !=(const max_t& a) const { return this->val != a.val; }

    void Print() const { cout << this->val << sp; }
    void log() const { cerr << this->val << sp; }
};
class min_t{
public:
    ll val;

    min_t(ll val = 0){ this->val = val; }
    static min_t null_v(){ return min_t(LINF); }

    static min_t op(const min_t& a, const min_t& b){ return min_t(min(a.val, b.val)); }
    // This is currently on set mode but it can be on add.
    min_t up(const min_t& a){ return *this = a; }
    void lazy_op(const min_t& a, int l){ up(a); }

    min_t operator =(const min_t& a){ this->val = a.val; return *this; }
    min_t operator +=(const min_t& a) { this->val += a.val; return *this; }
    min_t operator -=(const min_t& a) { this->val -= a.val; return *this; }
    min_t operator +(const min_t& a) const { return min_t(this->val + a.val); }
    min_t operator -(const min_t& a) const { return min_t(this->val - a.val); }
    bool operator ==(const min_t& a) const { return this->val == a.val; }
    bool operator !=(const min_t& a) const { return this->val != a.val; }

    void Print() const { cout << this->val << sp; }
    void log() const { cerr << this->val << sp; }
};
class lca{
private:
    int n, _edges_ = 0;
    vector<int> depth;
    vector<vector<int> > g, par;
    bool _initialized_ = 0, _computed_ = 0;
    void init(int n){
        this->n = n;
        this->depth = vector<int>(n);
        this->g = vector<vector<int> >(n);
        this->par = vector<vector<int> >(n, vector<int>(lg(n)+10, -1));
        this->_initialized_ = 1;
    }
    void dfs(int s, int p, int d){
        this->depth[s] = d;
        this->par[s][0] = p;
        for (int u : this->g[s])
            if (u^p)
                dfs(u, s, d+1);
    }
public:
    lca(){}
    lca(int n){ init(n); }
    void add(int u, int v){
        if (!this->_initialized_){
            cerr << "Initialize tree u idiot!" << endl;
            exit(1);
        }

        this->g[u].pb(v);
        this->g[v].pb(u);
        this->_edges_++;
    }
    void Compute(int root = 0){
        if (this->_edges_ < this->n-1){
            cerr << "Constructed tree is not connected!" << endl;
            exit(1);
        }
        if (this->_edges_ > this->n-1){
            cerr << "Constructed tree has cycles!" << endl;
            exit(1);
        }

        dfs(root, -1, 0);
        for (int d = 1; d < lg(this->n)+1; d++)
            for (int s = 0; s < this->n; s++)
                if (this->depth[s] >= (1<<d))
                    this->par[s][d] = this->par[this->par[s][d-1]][d-1];
        _computed_ = 1;
    }
    int Depth(int s) const {
        if (!this->_computed_){
            cerr << "Lca table has not been computed yet!" << endl;
            exit(1);
        }
        return this->depth[s];
    }
    int Par(int s, int d) const {

        if (!this->_computed_){
            cerr << "Lca table has not been computed yet!" << endl;
            exit(1);
        }
        if (d < 0 || d > this->depth[s]) return -1;
        if (!d) return s;
        return Par(this->par[s][lg(d)], d-highpow(d));
    }
    int Lca(int u, int v) const {

        if (!this->_computed_){
            cerr << "Lca table has not been computed yet!" << endl;
            exit(1);
        }
        if (this->depth[u] > this->depth[v]) swap(u, v);
        v = Par(v, this->depth[v] - this->depth[u]);
        if (u==v) return v;
        for (int i = lg(this->n)+1; ~i; i--){
            if (this->par[u][i]^this->par[v][i]){
                u = this->par[u][i];
                v = this->par[v][i];
            }
        }
        return this->par[u][0];
    }
    int Dist(int u, int v) const {

        if (!this->_computed_){
            cerr << "Lca table has not been computed yet!" << endl;
            exit(1);
        }
        int s = Lca(u, v);
        return this->depth[u] + this->depth[v] - 2*this->depth[s];
    }
    void Log() const {

        if (!this->_computed_){
            cerr << "Lca table has not been computed yet!" << endl;
            exit(1);
        }
        for (int s = 0; s < this->n; s++){
            cerr << s << tb;
            for (int d = 0; d < lg(this->n)+1; d++)
                cerr << this->par[s][d] << sp;
            cerr << endl;
        }
    }
};
struct Query{

    int t;
    int u, v;
    int l, r, x;
};
ll n, q, m, a[mxN];
segtree<min_t>* st_min;
segtree<max_t>* st_max;
lca* lc;
Query queries[mxN];
vector<int> g[mxN];

void SolveChain(){

    int mp[n];
    int s = 0;
    for (int i = 0; i < n; i++)
        if (g[i].size() == 1)
            s = i;
    int p = -1, in = 0;
    do{
        mp[s] = in++;
        int v;
        for (int u : g[s])
            if (u^p)
                v = u;
        p = s;
        s = v;
    } while (g[s].size()^1);
    mp[s] = in;
    for (int i = 0; i < n; i++)
        a[i] = mp[a[i]];
    st_min = new segtree<min_t>(n, a);
    st_max = new segtree<max_t>(n, a);
    for (int i = 0; i < q; i++){
        if (queries[i].t){
            int l = queries[i].l;
            int r = queries[i].r;
            int x = queries[i].x;
            x = mp[x];
            int mn = st_min->query(l, r);
            int mx = st_max->query(l, r);
            cout << max(abs(mn - x), abs(mx - x)) << en;
        }
        else{
            int t1 = queries[i].u;
            int t2 = queries[i].v;
            st_min->update(t1, t1, a[t2]);
            st_min->update(t2, t2, a[t1]);
            st_max->update(t1, t1, a[t2]);
            st_max->update(t2, t2, a[t1]);
            swap(a[t1], a[t2]);
        }
    }
}

void SolveX(int x){

    lc = new lca(n);
    for (int i = 0; i < n; i++)
        for (int u : g[i])
            if (u > i)
                lc->add(u, i);
    lc->Compute();
    for (int i = 0; i < n; i++)
        a[i] = lc->Dist(a[i], x);
    st_max = new segtree<max_t>(n, a);
    for (int i = 0; i < q; i++){
        if (queries[i].t){
            int l = queries[i].l;
            int r = queries[i].r;
            cout << st_max->query(l, r) << en;
        }
        else{
            int t1 = queries[i].u;
            int t2 = queries[i].v;
            st_max->update(t1, t1, a[t2]);
            st_max->update(t2, t2, a[t1]);
            swap(a[t1], a[t2]);
        }
    }
}

void Solve(){

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i], a[i]--;
    bool f = 1;
    for (int i = 0; i < n-1; i++){
        ri(u); ri(v);
        u--; v--;
        g[u].pb(v);
        g[v].pb(u);
        if (g[u].size() > 2 || g[v].size() > 2)
            f = 0;
    }
    cin >> q;
    set<int> s;
    for (int i = 0; i < q; i++){
        Query qr;
        cin >> qr.t; qr.t--;
        if (qr.t){
            cin >> qr.l >> qr.r >> qr.x;
            qr.l--; qr.r--; qr.x--;
            s.insert(qr.x);
        }
        else{
            cin >> qr.u >> qr.v;
            qr.u--; qr.v--;
        }
        queries[i] = qr;
    }
    if (f) SolveChain();
    else if (s.size() == 1) SolveX(*s.begin());
    else{
        lc = new lca(n);
        for (int i = 0; i < n; i++)
            for (int u : g[i])
                if (u > i)
                    lc->add(u, i);
        lc->Compute();
        for (int i = 0; i < q; i++){
            if (queries[i].t){
                int l = queries[i].l;
                int r = queries[i].r;
                int x = queries[i].x;
                int ans = 0;
                for (int j = l; j <= r; j++)
                    smax(ans, lc->Dist(x, a[j]));
                cout << ans << en;
            }
            else{
                int u = queries[i].u;
                int v = queries[i].v;
                swap(a[u], a[v]);
            }
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}