#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=80005;
int n,q,blk,t[N],l[N],r[N],p[N],a[N],b[N],x[N],cen[N],id[N];
VI e[N],g[N];

struct SegTree {
	VI st,all,nd;
	map<int,int> val;
	int n;
	SegTree() {}
	SegTree(int n) {
		st.resize(4*n);
		fill(all(st),-1e8);
	}
	void modify(int p,int l,int r,int qi,int x) {
		if (l>r||l>qi||r<qi) return;
		if (l==r) {
			st[p]=max(st[p],x);
			return;
		}
		int md=(l+r)>>1;
		modify(p+p,l,md,qi,x);
		modify(p+p+1,md+1,r,qi,x);
		st[p]=max(st[p],x);
	}
	int query(int p,int l,int r,int ql,int qr) {
		if (l>r||l>qr||r<ql) return -1e8;
		if (ql<=l&&r<=qr) return st[p];
		int md=(l+r)>>1;
		return max(query(p+p,l,md,ql,qr),query(p+p+1,md+1,r,ql,qr));
	}
	void build() {
		sort(all(all));
		all.erase(unique(all(all)),all.end());
		n=SZ(all);
		st.resize(4*n);
		fill(all(st),-1e8);
		int tsz=0;
		for (auto x:all) val[x]=tsz,tsz++;
		/*for (auto x:kk) {
			//modify(1,0,n-1,val[x.fi],x.se);		
		}*/
	}
}ST[N];

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

void dfssz(int u,int f) {
	sz[u]=1;
	for (int v:e[u]) {
		if (v==f||vis[v]) continue;
		dfssz(v,u);
		sz[u]+=sz[v];
	}
}

int find(int u,int f,int m) {
	for (int v:e[u]) {
		if (v!=f&&!vis[v]&&sz[v]*2>=m) return find(v,u,m);
	}
	return u;
}

/*void dfs2(int u,int f,int x) {
	g[u].pb(x); g[x].pb(u);
	if (u!=x) par[u][0]=x;
	dep[u]=dep[f]+1;
	for (int v:e[u]) {
		if (v==f||vis[v]) continue;
		dfs2(v,u,x);
	}
}*/

int R;
VI ch[N];

void dfs1(int u,int f) {
	dfssz(u,u);
	u=find(u,u,sz[u]);
	vis[u]=1;
	if (f>0) {
		cen[u]=f;
	} else {
		R=u;
	}
	if (f>0) {
		g[u].pb(f); ch[f].pb(u);
	}
	for (int v:e[u]) {
		if (v==f||vis[v]) continue;
		dfs1(v,u);
	}
}

void dfs0(int u,int f) {
	par[u][0]=f;
	dep[u]=dep[f]+1;
	for (int v:e[u]) {
		if (v==f) continue;
		dfs0(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[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
	return (u==v?u:par[u][0]);
}

int lift(int u,int k) {
	per(i,0,LOGN) if ((k>>i)&1) u=par[u][i];
	return u;
}

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








vector<PII> qs[N];
VI spec[N];
int mx[N],wh[N];

void gao(int u) {
	int deg=SZ(ch[u]);
	rep(i,0,deg) wh[ch[u][i]]=i;
	vector<VI> pos(deg);
	for (auto qq:qs[u]) {
		pos[wh[qq.se]].pb(qq.fi);
		if (u==R) {
			//printf("bruh      %d %d\n",qq.fi,qq.se);
		}
	}

	int PQ=SZ(ST[u].all);
	//printf("moj te pipo: %d %d\n",u,PQ);
	SegTree L(PQ),R(PQ);

	rep(i,0,SZ(ch[u])) {
		gao(ch[u][i]);
		for (auto qq:pos[i]) {
			//printf("%d\n",L.query(1,0,PQ-1,ST[u].val[l[qq]],ST[u].val[r[qq]]));
			if (!have[u]) {
				if (id[u]>=l[qq]&&id[u]<=r[qq]) mx[qq]=max(mx[qq],dist(x[qq],u));
			}
			mx[qq]=max(mx[qq],L.query(1,0,PQ-1,ST[u].val[l[qq]],ST[u].val[r[qq]])+dist(u,x[qq]));
		}
		for (auto x:ST[ch[u][i]].nd) {
			if (!have[x]) {
				L.modify(1,0,PQ-1,ST[u].val[id[x]],dist(u,x));
				//printf("modify: %d  %d %d\n",u,x,dist(u,x));
			}
		}
		int ww=ch[u][i];
		if (!have[ww]) {
			L.modify(1,0,PQ-1,ST[u].val[id[ww]],dist(u,ww));
		}
	}

	per(i,0,SZ(ch[u])) {
		for (auto qq:pos[i]) {
			mx[qq]=max(mx[qq],R.query(1,0,PQ-1,ST[u].val[l[qq]],ST[u].val[r[qq]])+dist(u,x[qq]));
		}
		for (auto x:ST[ch[u][i]].nd) {
			if (!have[x]) R.modify(1,0,PQ-1,ST[u].val[id[x]],dist(u,x));
		}
	}

	//printf("sada sam u: %d  have[u]: %d\n\n",u,have[u]);
	//if (have[u]) return;


	//printf("solvam    %d   %d\n",u,u);
	for (auto qq:spec[u]) {
		mx[qq]=max(mx[qq],L.query(1,0,PQ-1,ST[u].val[l[qq]],ST[u].val[r[qq]])+dist(x[qq],u));
	}
}
	
void add_query(int qid) {
	int u=x[qid],prv=x[qid];
	spec[u].pb(qid);
	//if (qid==2) printf("kveri 2: %d\n",u);
	ST[u].all.pb(l[qid]);
	ST[u].all.pb(r[qid]);
	ST[u].all.pb(id[x[qid]]);

	while (u!=0) {
		u=cen[u];
		if (u!=0) {
			ST[u].all.pb(l[qid]);
			ST[u].all.pb(r[qid]);
			ST[u].all.pb(id[x[qid]]);
			qs[u].pb({qid,prv});
		}
		prv=u;
	}
}

void ins_cen(int u) {
	int x=u;
	while (x>0) {
		//if (!have[u]) {
			ST[x].all.pb(id[u]);
			//ST[x].kk.pb({id[u],dist(u,x)});
			ST[x].nd.pb(u);
		//}
		x=cen[x];
	}
}

int main() {
	scanf("%d",&n);
	rep(i,1,n+1) scanf("%d",p+i);
	blk=605; // iskreno se nadam da prolazi
	rep(i,1,n) {
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].pb(v); e[v].pb(u);
	}
	dfs1(1,0);
	dfs0(1,0);
	scanf("%d",&q);
	rep(i,1,q+1) {
		scanf("%d",t+i);
		if (t[i]==1) scanf("%d%d",a+i,b+i);
		else scanf("%d%d%d",l+i,r+i,x+i);
	}
	//rep(i,1,n+1) printf("%d\n",par[i][0]);
	rep(j,1,LOGN) rep(i,1,n+1) par[i][j]=par[par[i][j-1]][j-1];

	//printf("cen: "); rep(i,1,n+1) printf("%d ",cen[i]); puts("");

	/*rep(i,1,n+1) {
		printf("cen %d: ",i);
		for (auto sta:ch[i]) printf("%d ",sta);
		puts("");
	}*/

	rep(bid,0,(q+blk-1)/blk) {
		//printf("p = "); rep(i,1,n+1) printf("%d ",p[i]); puts("");
		rep(i,1,n+1) {
			have[i]=0;
			id[p[i]]=i; 
			ST[i].all.clear();
			ST[i].val.clear();
			qs[i].clear();
			spec[i].clear();
		}

		//rep(i,1,n+1) printf("%d ",p[i]); puts("");
		int ql=bid*blk+1,qr=min(q,(bid+1)*blk);

		//printf("hello: %d %d\n",ql,qr);
		rep(i,ql,qr+1) if (t[i]==1) {
			have[p[a[i]]]=1;
			have[p[b[i]]]=1;
		}
		rep(i,ql,qr+1) {
			if (t[i]==1) {
				have[p[a[i]]]=1;
				have[p[b[i]]]=1;
			} else {
				add_query(i);
			}
		}
		rep(i,1,n+1) if (!have[i]) ins_cen(i);
		rep(i,1,n+1) ST[i].build();
		gao(R);
		VI v;
		rep(i,1,n+1) if (have[i]) v.pb(i);
		

		rep(i,ql,qr+1) {
			if (t[i]==1) swap(p[a[i]],p[b[i]]),swap(id[p[a[i]]],id[p[b[i]]]);
			else {
				int ans=mx[i];
				for (auto q:v) {
					if (id[q]>=l[i]&&id[q]<=r[i]) {
						ans=max(ans,dist(x[i],q));
					}
 				}
				printf("%d\n",ans);
			}
		}
	}
}