树上带修改莫队算法，对于维护mex值，可以使用修改$O(1)$，查询$O(sqrt{n})$的权值分块，总时间复杂度为$O(n^frac{5}{3})$。
#include<cstdio>
#include<algorithm>
#define N 50010
#define K 15
using namespace std;
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
struct Que{int l,r,t,z;}ask[N];
int ans[N];
int n,m,q,i,j,k,x,y,z,f[N][16],d[N],B,nl,nr,l,r,vis[N],C[N],c[N];
int T,mx[N],my[N],op[N];
int st[N],en[N],dfn[N<<1],pos[N<<1],post,g[N],v[N<<1],nxt[N<<1],ed,que[50][50],fin[50][50];
int ap[N],h[N],full[N],now[N];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,int pre){
dfn[st[x]=++post]=x;
int i=1;
for(f[x][0]=pre;i<=K;i++)f[x][i]=f[f[x][i-1]][i-1];
for(i=g[x];i;i=nxt[i])if(v[i]!=pre)d[v[i]]=d[x]+1,dfs(v[i],x);
dfn[en[x]=++post]=x;
}
inline int lca(int x,int y){
if(x==y)return x;
if(d[x]<d[y])swap(x,y);
for(int i=K;~i;i--)if(d[f[x][i]]>=d[y])x=f[x][i];
if(x==y)return x;
for(int i=K;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
inline void addq(int x,int y,int z){
v[++ed]=z;nxt[ed]=0;
if(!que[x][y])que[x][y]=ed;else nxt[fin[x][y]]=ed;
fin[x][y]=ed;
}
inline void deal(int x){
if(c[x]<=n){
if(vis[x]){
ap[c[x]]--;
if(!ap[c[x]])now[pos[c[x]]]--;
}else{
if(!ap[c[x]])now[pos[c[x]]]++;
ap[c[x]]++;
}
}
vis[x]^=1;
}
inline int askmex(){for(int i=0;;i++)if(full[i]>now[i])for(int j=h[i];;j++)if(!ap[j])return j;}
int main(){
read(n);read(q);
for(i=1;i<=n;i++)read(C[i]);
for(i=1;i<n;i++)read(x),read(y),add(x,y),add(y,x);
dfs(d[1]=1,ed=0);
while(B*B*B<post)B++;B*=B;
for(i=1;i<=post;i++)pos[i]=(i-1)/B+1;m=pos[post];
for(i=1;i<=q;i++){
read(op[i]);read(x);read(y);
if(!op[i])mx[++T]=x,my[T]=y;
else{
if(st[x]>st[y])swap(x,y);
z=lca(x,y);
if(z==x)nl=st[x],nr=st[y];else nl=en[x],nr=st[y];
ask[i].t=T;
ask[i].l=nl;ask[i].r=nr;
if(z!=x)ask[i].z=z;
addq(pos[nl],pos[nr],i);
}
}
for(B=1;B*B<=n;B++);
for(i=1;i<=n;i++)pos[i]=(i-1)/B+1;
for(i=0;i<=n;i++)full[pos[i]]++;
for(i=n;i;i--)h[pos[i]]=i;
for(i=1;i<=m;i++)for(j=i;j<=m;j++)if(que[i][j]){
for(k=0;k<=n;k++)c[k]=C[k],vis[k]=ap[k]=0;
for(k=0;k<=pos[n];k++)now[k]=0;
T=1;l=(i-1)*B+1;r=l-1;
for(k=que[i][j];k;k=nxt[k]){
if(r<ask[v[k]].r){for(r++;r<=ask[v[k]].r;r++)deal(dfn[r]);r--;}
if(r>ask[v[k]].r)for(;r>ask[v[k]].r;r--)deal(dfn[r]);
if(l<ask[v[k]].l)for(;l<ask[v[k]].l;l++)deal(dfn[l]);
else if(l>ask[v[k]].l){for(l--;l>=ask[v[k]].l;l--)deal(dfn[l]);l++;}
while(T<=ask[v[k]].t){
bool flag=(ask[v[k]].l<=st[mx[T]]&&st[mx[T]]<=ask[v[k]].r)^(ask[v[k]].l<=en[mx[T]]&&en[mx[T]]<=ask[v[k]].r);
if(flag)deal(mx[T]);
c[mx[T]]=my[T];
if(flag)deal(mx[T]);
T++;
}
if(ask[v[k]].z)deal(ask[v[k]].z);
ans[v[k]]=askmex();
if(ask[v[k]].z)deal(ask[v[k]].z);
}
}
for(i=1;i<=q;i++)if(op[i])printf("%d
",ans[i]);
return 0;
}