Description
Haruna每天都会给提督做早餐！ 这天她发现早饭的食材被调皮的 Shimakaze放到了一棵
树上，每个结点都有一样食材，Shimakaze要考验一下她。
每个食材都有一个美味度，Shimakaze会进行两种操作：
1、修改某个结点的食材的美味度。
2、对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。
请你帮帮Haruna吧。
Input
第一行包括两个整数n，m，代表树上的结点数(标号为1~n)和操作数。
第二行包括n个整数a1...an，代表每个结点的食材初始的美味度。
接下来n-1行，每行包括两个整数u，v，代表树上的一条边。
接下来m 行，每行包括三个整数
0 u x 代表将结点u的食材的美味度修改为 x。
1 u v 代表询问以u，v 为端点的链的mex值。
Output
对于每次询问，输出该链的mex值。
Sample Input
10 10
1 0 1 0 2 4 4 0 1 0
1 2
2 3
2 4
2 5
1 6
6 7
2 8
3 9
9 10
0 7 14
1 6 6
0 4 9
1 2 2
1 1 8
1 8 3
0 10 9
1 3 5
0 10 0
0 7 7
1 0 1 0 2 4 4 0 1 0
1 2
2 3
2 4
2 5
1 6
6 7
2 8
3 9
9 10
0 7 14
1 6 6
0 4 9
1 2 2
1 1 8
1 8 3
0 10 9
1 3 5
0 10 0
0 7 7
Sample Output
0
1
2
2
3
1
2
2
3
HINT
1<=n<=5*10^4
1<=m<=5*10^4
0<=ai<=10^9
还是树上带修莫队。
因为答案最多是n，所以>n的权值都设成n+1好了。
然后我们要实现这样一个集合：
1.加入一个元素
1.加入一个元素
2.删除一个元素
3.询问mex
因为修改次数很多而询问次数很少，所以我们对权值进行分块就可以在O(1)时间完成修改，O(sqrt(N))时间完成查询。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=<<;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
int x=,f=;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;
for(;isdigit(c);c=Getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int n,m,SIZE,val[maxn],first[maxn],next[maxn<<],to[maxn<<],e;
void AddEdge(int u,int v) {
to[++e]=v;next[e]=first[u];first[u]=e;
to[++e]=u;next[e]=first[v];first[v]=e;
}
int anc[maxn][],dep[maxn],S[maxn],blo[maxn],nu[maxn],top,ToT;
void dfs(int x,int fa) {
dep[x]=dep[anc[x][]=fa]+;nu[x]=top;
rep(i,,) anc[x][i]=anc[anc[x][i-]][i-];
ren if(to[i]!=fa) {
dfs(to[i],x);
if(top-nu[x]>SIZE) {
ToT++;while(top>nu[x]) blo[S[top--]]=ToT;
}
}
S[++top]=x;
}
int lca(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
dwn(i,,) if(<<i<=dep[x]-dep[y]) x=anc[x][i];
dwn(i,,) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
return x==y?x:anc[x][];
}
struct Query {
int x,y,t,id;
bool operator < (const Query& ths) const {
if(blo[x]!=blo[ths.x]) return blo[x]<blo[ths.x];
if(blo[y]!=blo[ths.y]) return blo[y]<blo[ths.y];
return t<ths.t;
}
}A[maxn];
int ans[maxn],cnt[maxn],vis[maxn],X[maxn],Y[maxn],Z[maxn],M,N;
int bel[maxn],st[maxn],en[maxn],bans[maxn];
void U(int x) {
int v=val[x];
if(!vis[x]) {
if(!cnt[v]) bans[bel[v]]++;
cnt[v]++;
}
else {
cnt[v]--;
if(!cnt[v]) bans[bel[v]]--;
}
vis[x]^=;
}
void update(int x,int v) {
v=min(v,n+);
if(vis[x]) U(x),val[x]=v,U(x);
else val[x]=v;
}
void move(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]!=dep[y]) U(x),x=anc[x][];
while(x!=y) U(x),U(y),x=anc[x][],y=anc[y][];
}
int query() {
rep(i,,bel[n+]) if(bans[i]!=en[i]-st[i]+) {
rep(j,st[i],en[i]) if(!cnt[j]) return j;
return -;
}
}
void init() {
int SIZE2=(int)sqrt(n);
rep(i,,n+) {
bel[i]=i/SIZE2+;
en[bel[i]]=i;
if(!i||bel[i]!=bel[i-]) st[bel[i]]=i;
}
}
int main() {
n=read();m=read();SIZE=(int)pow(n,0.666)*0.7;
rep(i,,n) val[i]=min(n+,read());
rep(i,,n) AddEdge(read(),read());
dfs(,);ToT++;rep(i,,top) blo[S[i]]=ToT;
memset(ans,-,sizeof(ans));init();
rep(i,,m) {
int t=read(),x=read(),y=read();
if(!t) X[++M]=x,Y[M]=val[x],val[x]=Z[M]=y;
else {
if(blo[x]>blo[y]) swap(x,y);
A[++N]=(Query){x,y,M,i};
}
}
sort(A+,A+N+);
int cu=,cv=,t=M;
rep(i,,N) {
int x=A[i].x,y=A[i].y,z=lca(x,y);
while(t<A[i].t) t++,update(X[t],Z[t]);
while(t>A[i].t) update(X[t],Y[t]),t--;
move(cu,x);move(cv,y);cu=x;cv=y;
U(z);ans[A[i].id]=query();U(z);
}
rep(i,,m) if(ans[i]>=) printf("%d\n",ans[i]);
return ;
}