#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
 
#define ff(i,a,b) for(int i = a; i <= b; i++)
#define fb(i,b,a) for(int i = b; i >= a; i--)
#define trav(a,x) for (auto& a : x)
 
#define sz(a) (int)(a).size()
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

const int mod = 1000000007;
const int inf = 1e9 + 5;
const int mxN = 80005; 

int n, q;
int niz[mxN];

vector<int> g[mxN];

vector<int> euler;

int d[mxN];
int in[mxN];
void dfs(int v, int p) {
    in[v] = sz(euler);
    euler.pb(v);
    for(auto u : g[v]) {
        if(u != p) {
            d[u] = d[v] + 1;
            dfs(u, v);
            euler.pb(v);
        }
    }
}

int cmb(int X, int Y) {
    return (d[X] > d[Y] ? Y : X);
}

int sp[10 * mxN][20];
void init_sp() {
    int N = sz(euler);
    ff(i,0,N - 1)sp[i][0] = euler[i];
    ff(j,1,19) {
        for(int i = 0; i + (1 << j) - 1 < N; i++) {
            sp[i][j] = cmb(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int rmq(int l, int r) {
    int x = 31 - __builtin_clz(r - l + 1);
    return cmb(sp[l][x], sp[r - (1 << x) + 1][x]);
}

int lca(int x, int y) {
    x = in[x], y = in[y];
    if(x > y)swap(x, y);
    return rmq(x, y);
}

int dist(int x, int y){
	if(x == 0 || y == 0)return -inf;
	return d[x] + d[y] - 2 * d[lca(x, y)];
}	

struct SegTree{
	pii bor[4 * mxN];

	pii comb(pii A, pii B){
		pii C = {0, 0}; int mx = -inf;

		int X = dist(A.fi, B.fi);
		if(X > mx){
			mx = X;
			C = {A.fi, B.fi};
		}

		X = dist(A.fi, B.se);
		if(dist(A.fi, B.se) > mx){
			mx = X;
			C = {A.fi, B.se};
		}

		X = dist(A.se, B.fi);
		if(X > mx){
			mx = X;
			C = {A.se, B.fi};
		}
	
		X = dist(A.se, B.se);	
		if(X > mx){
			mx = X;
			C = {A.se, B.se};
		}

		X = dist(A.fi, A.se);
		if(X > mx){
			mx = X;
			C = {A.fi, A.se};
		}

		X = dist(B.fi, B.se);
		if(X > mx){
			mx = X;
			C = {B.fi, B.se};
		}

		return C;

	}

	void build(int v, int tl, int tr){
		if(tl == tr){
			bor[v] = {niz[tl], niz[tl]};
			return;
		}
		int mid = (tl + tr) / 2;
		build(v * 2, tl, mid); build(v * 2 + 1, mid + 1, tr);
		bor[v] = comb(bor[v * 2], bor[v * 2 + 1]);
	}

	void update(int v, int tl, int tr, int pos, int val){
		if(tl == tr){
			bor[v] = {val, val};
			return;
		}
		int mid = (tl + tr) / 2;
		if(pos <= mid)update(v * 2, tl, mid, pos, val);
		else update(v * 2 + 1, mid + 1, tr, pos, val);
		bor[v] = comb(bor[v * 2], bor[v * 2 + 1]);
	}

	pii kveri(int v, int tl, int tr, int l, int r){
		if(tl > r || l > tr)return {0, 0};
		if(tl >= l && tr <= r)return bor[v];
		int mid = (tl + tr) / 2;
		pii A = kveri(v * 2, tl, mid, l, r);
		pii B = kveri(v * 2 + 1, mid + 1, tr, l, r);
		pii C = comb(A, B);
		return C;
	}
}drvo;



int main() {
    cin.tie(0)->sync_with_stdio(0);

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

    dfs(1, 0); init_sp();
    drvo.build(1,1,n);

    cin >> q;
    while(q--){
    	int t;
    	cin >> t;

    	if(t == 1){
    		int a, b;
    		cin >> a >> b;

    		drvo.update(1,1,n,a,niz[b]);
    		drvo.update(1,1,n,b,niz[a]);
    		swap(niz[a], niz[b]);

    	}

    	if(t == 2){
    		int l, r, x;
    		cin >> l >> r >> x;

    		pii A = drvo.kveri(1,1,n,l,r);
    		cout << max(dist(A.fi, x), dist(A.se, x)) << '\n';

    	}

    }

    return 0;
}
/*

10
7 8 2 4 5 1 3 10 6 9 
2 1
3 1
4 1
5 2
6 1
7 2
8 6
9 1
10 1
1
2 2 7 10

 
// probati bojenje sahovski
*/