按照dfs序分块，莫队乱搞
再套个权值分块
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 100005
using namespace std;
int e=1,head[N];
struct edge{
int u,v,next;
}ed[2*N];
void add(int u,int v){
ed[e].u=u; ed[e].v=v;
ed[e].next=head[u];
head[u]=e++;
}
int qq,cc,n,m,nn,nnn,be[N],bb[N],gy[N],dep[N],fa[N],anc[N][18];
bool vis[N];
int num[N],all[N],ll[N],rr[N];
struct Query{
int l,r,id,tim,ans;
}qr[N];
void add_query(int x,int y){
qr[++qq].l=x;
qr[qq].r=y;
qr[qq].id=qq;
qr[qq].tim=cc;
}
bool cmp1(Query a,Query b){
if(be[a.l]==be[b.l])
return be[a.r]<be[b.r];
return be[a.l]<be[b.l];
}
bool cmp2(Query a,Query b){
return a.id<b.id;
}
struct Change{
int pos,nxt,pre;
}ch[N];
void add_change(int x,int y){
ch[++cc].pos=x;
ch[cc].nxt=y;
ch[cc].pre=gy[x];
gy[x]=y;
}
int stack[N],top=0,cnt;
void dfs(int x){
dep[x]=dep[fa[x]]+1;
for(int i=1;i<=15;i++)
anc[x][i]=anc[anc[x][i-1]][i-1];
for(int i=head[x];i;i=ed[i].next){
int v=ed[i].v;
if(v==fa[x]) continue;
fa[v]=anc[v][0]=x;
dfs(v);
if(top>=nn){
++cnt;
while(top)
be[stack[top--]]=cnt;
}
}
stack[++top]=x;
if(x==1&&top){
++cnt;
while(top)
be[stack[top--]]=cnt;
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);//dep[x]>=dep[y]
for(int i=15;~i;i--)
if(dep[anc[x][i]]>=dep[y])
x=anc[x][i];
if(x==y) return x;
for(int i=15;~i;i--)
if(anc[x][i]!=anc[y][i]){
x=anc[x][i];
y=anc[y][i];
}
return anc[x][0];
}
void pls(int x){
vis[x]=1;
if(gy[x]>n+1) return;
if(++num[gy[x]]==1)
all[bb[gy[x]]]++;
}
void reduc(int x){
vis[x]=0;
if(gy[x]>n) return;
if(--num[gy[x]]==0)
all[bb[gy[x]]]--;
}
void update(int x){
if(vis[x]){
reduc(x);
return ;
}
if(!vis[x]) pls(x);
}
void change(int x,int y){
int now=lca(x,y);
//printf("x==%d y==%d now==%d
",x,y,now);
while(x!=now)
update(x),x=fa[x];
while(y!=now)
update(y),y=fa[y];
}
int main()
{
scanf("%d%d",&n,&m);
nn=(int)pow(n,2.0/3.0);
nnn=(int)sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&gy[i]);
bb[i]=i/nnn+1;
}
bb[0]=1;
for(int i=1;i<=bb[n];i++){
ll[i]=(i-1)*nnn;
rr[i]=i*nnn-1;
}
int u,v;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs(1);
int opt,a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&opt,&a,&b);
if(opt==0) add_change(a,b);
if(opt==1) add_query(a,b);
}
sort(qr+1,qr+qq+1,cmp1);
int l=1,r=1,t=cc,old,now;
update(1);
for(int i=1;i<=qq;i++)
{
//printf("%d %d %d %d
",qr[i].id,qr[i].tim,qr[i].l,qr[i].r);
old=lca(l,r);
now=lca(qr[i].l,qr[i].r);
change(qr[i].l,l);
change(qr[i].r,r);
update(old); update(now);
for(int j=t+1;j<=qr[i].tim;j++){
if(dep[ch[j].pos]>=dep[now]&&(lca(ch[j].pos,qr[i].l)==ch[j].pos||lca(ch[j].pos,qr[i].r)==ch[j].pos)){
update(ch[j].pos); gy[ch[j].pos]=ch[j].nxt; update(ch[j].pos);
}
gy[ch[j].pos]=ch[j].nxt;
}
for(int j=t;j>qr[i].tim;j--){
if(dep[ch[j].pos]>=dep[now]&&(lca(ch[j].pos,qr[i].l)==ch[j].pos||lca(ch[j].pos,qr[i].r)==ch[j].pos)){
update(ch[j].pos); gy[ch[j].pos]=ch[j].pre; update(ch[j].pos);
}
gy[ch[j].pos]=ch[j].pre;
}
t=qr[i].tim; l=qr[i].l; r=qr[i].r;
for(int j=1;j<=bb[n];j++)
if(all[j]!=rr[j]-ll[j]+1){
for(int k=ll[j];k<=rr[j];k++){
if(!num[k]){
qr[i].ans=k;
break;
}
}
break;
}
//for(int j=0;j<=n;j++) printf("k==%d num==%d
",j,num[j]);
//printf("ans================%d
",qr[i].ans);
}
sort(qr+1,qr+qq+1,cmp2);
for(int i=1;i<=qq;i++)
printf("%d
",qr[i].ans);
return 0;
}