第二道树上莫队。。
这个的话要对数值进行分块才可以跑
其实也差不是太多
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=100005;
int n,m,q;
int block;
int val[N],w[N];
int c[N],pre[N];
struct ask{int l,r,t,lb,rb,id;}a[N];
struct UP{int x,y,pre;}b[N];
int cnt2=0,cnt1=0;
struct qq{int x,y,last;}s[N*2];int num,last[N];
void init (int x,int y)
{num++;s[num].x=x;s[num].y=y;s[num].last=last[x];last[x]=num;
}
int dep[N],cc=0;
int f[N][20];
int sta[N],top=0;
int belong[N],ecnt=0;
bool vis[N];//是否在莫队里面
int dfs (int x,int fa)
{int remain=0;for (int u=last[x];u!=-1;u=s[u].last){int y=s[u].y;if (y==fa) continue;f[y][0]=x;dep[y]=dep[x]+1;remain+=dfs(y,x);if (remain>=block){ecnt++;while (remain>0) belong[sta[top--]]=ecnt,remain--;}}sta[++top]=x;return remain+1;
}
bool cmp(ask q,ask qq)
{if(q.lb==qq.lb && q.rb==qq.rb) return q.t<qq.t;if(q.lb==qq.lb) return q.rb<qq.rb;return q.lb<qq.lb;
}
int AA[N],BB[N],Belong[N],L[N],shen;//这个块有多少个元素 这个数字出现了多少次 这个数字时哪一个块的 这一个块的左边界
void prepare ()//分块
{shen=1;L[1]=0;AA[shen]=0;int cnt=0;for (int u=0;u<=n;u++){cnt++;BB[u]=0;Belong[u]=shen;if (cnt==block){cnt=0;shen++;AA[shen]=0;L[shen]=u+1;}}
}
void update (int x)//改变这个点的状态
{if (c[x]>n) return ;if (vis[x])//这个在莫队里面{//printf("-%d %d\n",c[x],BB[c[x]]);vis[x]=false;BB[c[x]]--;if (BB[c[x]]==0) AA[belong[c[x]]]--;}else{//printf("+%d %d\n",c[x],BB[c[x]]);vis[x]=true;BB[c[x]]++;if (BB[c[x]]==1) AA[belong[c[x]]]++;}
/* for (int u=0;u<=shen;u++) printf("%d ",AA[u]);printf("\n");*/
}
void lalal (int x,int C)//将x修改为C
{if (!vis[x]) c[x]=C;else{update(x);c[x]=C;update(x);}
}
void change (int x,int y)//加上这个路径 但是LCA还不在
{while (x!=y){if (dep[x]<dep[y]) update(y),y=f[y][0];else update(x),x=f[x][0];}
}
int A[N];
int lca (int x,int y)
{if (dep[x]>dep[y]) swap(x,y);for (int u=18;u>=0;u--) if (dep[f[y][u]]>=dep[x]) y=f[y][u];if (x==y) return x;for (int u=18;u>=0;u--)if (f[y][u]!=f[x][u])y=f[y][u],x=f[x][u]; return f[x][0];
}
int Get ()
{int x=1;while (AA[x]==block) x++;x=L[x];while (BB[x]!=0) x++;return x;
}
void solve ()
{sort(a+1,a+1+cnt1,cmp);cnt2=a[1].t;memset(vis,false,sizeof(vis));for (int u=1;u<=a[1].t;u++) lalal(b[u].x,b[u].y);change(a[1].l,a[1].r);//printf("ans:%d\n",Get());int LCA=lca(a[1].l,a[1].r);update(LCA);//可以知道，我们这条链还少了LCAA[a[1].id]=Get();update(LCA);//这里的目的是为了下一次的跳，可以知道，当我们更改的是后，l,r的路径要是空，否则会有多算for (int u=2;u<=cnt1;u++){while (cnt2<a[u].t) cnt2++,lalal(b[cnt2].x,b[cnt2].y);while (cnt2>a[u].t) lalal(b[cnt2].x,b[cnt2].pre),cnt2--;change(a[u].l,a[u-1].l);change(a[u].r,a[u-1].r);LCA=lca(a[u].l,a[u].r);update(LCA);A[a[u].id]=Get();// printf("ans:%d\n",Get());update(LCA);}
}
void ins ()
{num=0;memset(last,-1,sizeof(last));scanf("%d%d",&n,&q);block=(int)pow(n,0.60);for (int u=1;u<=n;u++) {scanf("%d",&c[u]);pre[u]=c[u];}for (int u=1;u<n;u++){int x,y;scanf("%d%d",&x,&y);init(x,y);init(y,x);}ecnt=0;dep[1]=1;dfs(1,0);for (int u=1;u<=17;u++)for (int i=1;i<=n;i++)f[i][u]=f[f[i][u-1]][u-1];for (int u=1;u<=q;u++){int op,x,y;scanf("%d%d%d",&op,&x,&y);if (op==0) {b[++cnt2].pre=pre[x];b[cnt2].x=x;b[cnt2].y=y;pre[x]=y;}else{a[++cnt1].l=x;a[cnt1].r=y;a[cnt1].lb=belong[x];a[cnt1].rb=belong[y];a[cnt1].t=cnt2;a[cnt1].id=cnt1;}}
}
int main()
{ins();prepare();//for (int u=0;u<=n;u++) printf("YES:%d %d\n",Belong[u],L[Belong[u]]);solve();for (int u=1;u<=cnt1;u++) printf("%lld\n",A[u]);return 0;
}