$rt$,代码如下：

#include<bits/stdc++.h>
using namespace std;
int read()
{
	char ch=getchar();
	int p=1;
	while(!('0'<=ch&&ch<='9'))
	{
		if(ch=='-') p=-1;
		ch=getchar();
	}
	int x=0;
	while('0'<=ch&&ch<='9')
	{
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*p;
}
int s[1500000],qw;
int n,qnn,bl2;
struct A
{
	int nxt,to;
}e[1500000];
int cnt,head[500000];
int a[500000];
void ad(int x,int y)
{
	cnt++;
	e[cnt].to=y;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}
struct B
{
	int x,v;
}g[500000];
struct C
{
	int l,r,t,k,lc,id;
}q[500000];
int num[500000],bn[5000],vs[500000];
int mx;
int bk[500000],tmp,dep[500000],in[500000],out[500000],f[200000][33],tot,bz[500000],vis[500000],ans[500000];
int rct[500000];
void inti()
{
	mx=n+qnn;
	bl2=sqrt(mx);
	for(int i=1;i<=mx;i++)
	{
		vs[i]=(i-1)/bl2+1;
	}
}
void dfs(int x,int fa)
{
	in[x]=++tmp,dep[x]=dep[fa]+1;
	bk[tmp]=x;
	f[x][0]=fa;
	for(int i=1;i<=20;i++)
	{
		f[x][i]=f[f[x][i-1]][i-1];
	}
	for(int i=head[x];i;i=e[i].nxt)
	{
		int to=e[i].to;
		if(to==fa) continue;
		dfs(to,x);
	}
	out[x]=++tmp,bk[tmp]=x;
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--)
	{
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	}
	if(x==y) return x;
	for(int i=20;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
bool cmp(C x,C y)
{
	if(vis[x.l]==vis[y.l])
	{
		if(vis[x.r]==vis[y.r])
		{
			return x.t<y.t;
		}
		if(vis[x.l]&1)
		{
			return x.r<y.r;
		}
		else
		{
			return x.r>y.r;
		}
	}
	return x.l<y.l;
}
void upd(int x)
{
	if(!x) return;
	x=bk[x];
	bz[x]^=1;
	int pos=bz[x]?1:-1;
	bn[vs[a[x]]]+=pos;
	num[a[x]]+=pos;
}
void upd2(int t,int hl,int hr)
{
	int x=g[t].x;
	if((hl<=in[x]&&in[x]<=hr)||(hl<=out[x]&&out[x]<=hr))
	{
		if(bz[x])
		{
			bn[vs[a[x]]]--;
			num[a[x]]--;
			bn[vs[g[t].v]]++;
			num[g[t].v]++;
		}
	}
	swap(a[x],g[t].v);
}
int main()
{
	scanf("%d%d",&n,&qnn);
	inti();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		s[++qw]=a[i];
	}
	for(int i=1;i<n;i++)
	{
		int x,y;
		x=read(),y=read();
		ad(x,y);
		ad(y,x);
	}
	dfs(1,0);
	int bl=pow(2*n,0.66667);
	for(int i=1;i<=n;i++)
	{
		vis[i]=(i-1)/bl+1;
	}
	int qn=0;
	for(int i=1;i<=qnn;i++)
	{
		int op,x,y;
		op=read(),x=read(),y=read();
		if(op==0)
		{
			s[++qw]=y;
			g[++tot].x=x;
			g[tot].v=y;
		}
		else
		{
			int lc=lca(x,y);
			if(in[x]>in[y])
			{
				swap(x,y);
			}
			if(lc==x)
			{
				q[++qn].l=in[x],q[qn].r=in[y],q[qn].t=tot,q[qn].k=op,q[qn].id=qn;
			}
			else
			{
				q[++qn].l=out[x],q[qn].r=in[y],q[qn].t=tot,q[qn].k=op,q[qn].id=qn,q[qn].lc=lc;
			}
		}
	}
	sort(s+1,s+1+qw);
	qw=unique(s+1,s+1+qw)-s-1;
	for(int i=1;i<=qw;i++)
	{
		rct[i]=s[i];
	}
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(s+1,s+1+qw,a[i])-s;
	}
	for(int i=1;i<=tot;i++)
	{
		g[i].v=lower_bound(s+1,s+1+qw,g[i].v)-s;
	}
	sort(q+1,q+1+qn,cmp);
	int l=0,r=0,t=0;
	for(int i=1;i<=qn;i++)
	{
		int hl=q[i].l,hr=q[i].r,ht=q[i].t;
		while(r<hr)
		{
			upd(++r);
		}
		while(r>hr)
		{
			upd(r--);
		}
		while(l<hl)
		{
			upd(l++);
		}
		while(l>hl)
		{
			upd(--l);
		}
		while(t<ht)
		{
			t++;
			upd2(t,hl,hr);
		}
		while(t>ht)
		{
			upd2(t,hl,hr);
			t--;
		}
		int sum=0,yu=-1;
		bn[vs[a[q[i].lc]]]++;
		num[a[q[i].lc]]++;
		for(int j=vs[mx];j>=1;j--)
		{
			sum+=bn[j];
			if(sum>=q[i].k)
			{
				yu=j;
				break;
			}
		}
		if(yu==-1)
		{
			bn[vs[a[q[i].lc]]]--;
			num[a[q[i].lc]]--;
			ans[q[i].id]=-1;
			continue;
		}
		sum-=bn[yu];
		int lim=min(yu*bl2,qw);
		for(int j=lim;j>=(yu-1)*bl2;j--)
		{
			sum+=num[j];
			if(sum>=q[i].k)
			{
				ans[q[i].id]=j;
				break;
			}
		}
		bn[vs[a[q[i].lc]]]--;
		num[a[q[i].lc]]--;
	}
	for(int i=1;i<=qn;i++)
	{
		if(ans[i]==-1)
		{
			printf("invalid request!\n");continue;
		}
		printf("%d\n",rct[ans[i]]);
	}
}