树上带修莫队的模板。
主要是查询的时候，一开始脑子抽了想log修改log查询显然会T到死，然而O1修改根号查询就好了，直接分块维护。
注意修改每次改回去的到时候改回的是上一次修改的颜色不是它本来的颜色，WA了好久。。。
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<ctime>
const int N=5e4+7;
typedef long long LL;
using namespace std;
int n,m,v[N],pr[N],is[N],ls[N],ans[N],sum[250],cnt[N],vis[N],cq,cc;
template<typename T> void read(T &x) {
T f=1; x=0; char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=-1,ch=getchar();
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}
int ecnt,fir[N],nxt[N<<1],to[N<<1];
void add(int u,int v) {
nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;
nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u;
}
int dfn[N],dfs_clock,sta[N],top,w,bl[N],R[N],f[N][20],tot;
void dfs(int x,int fa) {
dfn[x]=++dfs_clock;
R[x]=R[fa]+1;
f[x][0]=fa;
int low=top;
for(int i=1;i<20;i++)
f[x][i]=f[f[x][i-1]][i-1];
for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa) {
dfs(to[i],x);
if(top-low>=w) {
tot++;
while(top>low) {
int y=sta[top--];
bl[y]=tot;
}
}
}
sta[++top]=x;
}
struct node {
int x,y,ti;
node(){}
node(int x,int y,int ti):x(x),y(y),ti(ti){}
friend bool operator <(const node&A,const node&B) {
return bl[A.x]<bl[B.x]||(bl[A.x]==bl[B.x]&&bl[A.y]<bl[B.y]);
}
}qs[N],cg[N];
int qry() {
for(int i=0;i<=(n/w+1);i++)
if(sum[i]!=w)
for(int j=0;j<w;j++)
if(!cnt[i*w+j]) return i*w+j;
}
void rev(int x,int f) {
if(f) {
if(v[x]>=n) return;
cnt[v[x]]++;
if(cnt[v[x]]==1) sum[v[x]/w]++;
}
else {
if(v[x]>=n) return;
cnt[v[x]]--;
if(!cnt[v[x]]) sum[v[x]/w]--;
}
}
int lca(int x,int y) {
if(R[x]<R[y]) swap(x,y);
for(int i=19;i>=0;i--)
if(R[f[x][i]]>=R[y])
x=f[x][i];
if(x==y) return x;
for(int i=19;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
void change(int x,int y) {
int z=lca(x,y);
for(int i=x;i!=z;i=f[i][0])
rev(i,vis[i]^=1);
for(int i=y;i!=z;i=f[i][0])
rev(i,vis[i]^=1);
}
void solve() {
sort(qs+1,qs+cq+1);
int now=0;
for(int i=1;i<=cq;i++) {
while(now+1<=cc&&cg[now+1].ti<=qs[i].ti) {
now++;
if(vis[cg[now].x]) rev(cg[now].x,0);
v[cg[now].x]=cg[now].y;
if(vis[cg[now].x]) rev(cg[now].x,1);
}
while(now&&cg[now].ti>qs[i].ti) {
if(vis[cg[now].x]) rev(cg[now].x,0);
v[cg[now].x]=pr[now];
if(vis[cg[now].x]) rev(cg[now].x,1);
now--;
}
if(i==1) change(qs[i].x,qs[i].y);
else {
change(qs[i-1].x,qs[i].x);
change(qs[i-1].y,qs[i].y);
}
int z=lca(qs[i].x,qs[i].y);
rev(z,vis[z]^=1);
ans[qs[i].ti]=qry();
rev(z,vis[z]^=1);
}
}
int main() {
read(n); read(m);
for(int i=1;i<=n;i++) { read(v[i]); ls[i]=v[i];}
for(int i=1;i<n;i++) {
int u,v;
read(u); read(v);
add(u,v);
}
for(int i=1;i<=m;i++) {
int t,u,vv;
read(t); read(u); read(vv);
if(t==0) {
cg[++cc]=node(u,vv,i);
pr[cc]=ls[u]; ls[u]=vv;
is[i]=1;
}
else qs[++cq]=node(u,vv,i);
}
w=sqrt(n);
dfs(1,0);
if(top) tot++;
while(top) bl[sta[top--]]=tot;
sort(qs+1,qs+cq+1);
solve();
for(int i=1;i<=m;i++) if(!is[i]) printf("%d
",ans[i]);
return 0;
}
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<ctime>
using namespace std;
int main() {
srand(time(NULL));
int n=rand()%100+1,m=rand()%100+1;
printf("%d %d
",n,m);
for(int i=1;i<=n;i++) {
int x=rand()%n;
printf("%d ",x);
} puts("");
for(int i=2;i<=n;i++) {
int x=rand()%(i-1)+1;
printf("%d %d
",i,x);
}
for(int i=1;i<=m;i++) {
int t=rand()%2,x=rand()%n+1,y=rand()%n+1;
printf("%d %d %d
",t,x,y);
}
return 0;
}