#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=80500;
int n,q,p[N];
VI e[N];

struct node {
	VI v;
	node() {}
	node(VI sta) {
		v=sta;
	}
}nd[4*N];

#define LOGN 19
int par[N][LOGN],dep[N];

void dfs(int u,int f) {
	dep[u]=dep[f]+1;
	par[u][0]=f;
	for (int v:e[u]) {
		if (v==f) continue;
		dfs(v,u);
	}
}


int lca(int u,int v) {
	if (dep[u]>dep[v]) swap(u,v);
	per(i,0,LOGN) if (dep[par[v][i]]>=dep[u]) v=par[v][i];
	per(i,0,LOGN) if (par[v][i]!=par[u][i]) u=par[u][i],v=par[v][i];
	return (u==v?u:par[u][0]);
}

int dist(int u,int v) {
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}

VI comb(node x,node y) {
	vector<PII> svi;
	for (int i:x.v) {
		for (int j:y.v) {
			svi.pb(mp(i,j));
		}
	}
	int sz=SZ(svi);
	if (sz==0) {
		VI v;
		for (int i:x.v) v.pb(i);
		for (int i:y.v) v.pb(i);
		return v;	
	}
	VI p(sz);
	iota(all(p),0);
	sort(all(p),[&](int i,int j) {
		return dist(svi[i].fi,svi[i].se)>dist(svi[j].fi,svi[j].se);
	});
	VI ret;
	ret.pb(svi[p[0]].fi);
	ret.pb(svi[p[0]].se);
	return ret;
}

void build(int p,int l,int r) {
	if (l==r) {
		nd[p].v={::p[l]};
		return;
	}
	int md=(l+r)>>1;
	build(p+p,l,md);
	build(p+p+1,md+1,r);
	nd[p].v=comb(nd[p+p],nd[p+p+1]);
}

void update(int p,int l,int r,int qi) {
	if (l==r) {
		nd[p].v={::p[l]};
		return;
	}
	int md=(l+r)>>1;
	if (qi<=md) update(p+p,l,md,qi);
	else update(p+p+1,md+1,r,qi);
	nd[p].v=comb(nd[p+p],nd[p+p+1]);
}

node query(int p,int l,int r,int qs,int qe) {
	if (l>r||l>qe||r<qs) return node(VI{});
	if (qs<=l&&r<=qe) return nd[p];
	int md=(l+r)>>1;
	VI tot=comb(query(p+p,l,md,qs,qe),query(p+p+1,md+1,r,qs,qe));
	return node(tot);
}

int main() {
	scanf("%d",&n);
	rep(i,1,n+1) scanf("%d",p+i);
	rep(i,1,n) {
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].pb(v); e[v].pb(u);
	}
	dfs(1,0);
	per(j,1,LOGN) rep(i,1,n+1) par[i][j]=par[par[i][j-1]][j-1];
	build(1,1,n);
	scanf("%d",&q);
	while (q--) {
		int t;
		scanf("%d",&t);
		if (t==1) {
			int a,b;
			scanf("%d%d",&a,&b);
			swap(p[a],p[b]);
			update(1,1,n,a);
			update(1,1,n,b);
		} else {
			int l,r,x;
			scanf("%d%d%d",&l,&r,&x);
			VI sta=query(1,1,n,l,r).v;
			int ans=0;
			for (int qq:sta) {
				ans=max(ans,dist(qq,x));
			}
			printf("%d\n",ans);
		}
	}
}