题目大意：给定一棵树，，每个点有一个非负点权，支持下列操作 1.修改某个点的点权 2.查询某条链上的mex 考虑链上不带修改的版本，我们可以用莫队+分块来搞(链接戳这里) 现在到了树上带修改，果断糖果公园 本来抱着逗比的心态写了一发结果1.4s过了 跟糖果公园的80s完全不成正比啊0.0
;struct abcd{int to,next;}table[M<<1];int head[M],tot;int n,m,b1,b2,q,c,L=1,R=1,t;int fa[M],ancestor[M][16],dpt[M];int a[M],cnt[M],block[M];bool v[M];int belong[M],_cnt;struct Modifiction{int x,from,to,t;}modifictions[M];struct Query{int x,y,t,ans;bool operator < (const Query &q) const{if( belong[x] != belong[q.x] )return belong[x] < belong[q.x];if( belong[y] != belong[q.y] )return belong[y] < belong[q.y];return t < q.t ;}}queries[M];bool Compare(const Query &q1,const Query &q2){return q1.t < q2.t ;}void Add(int x,int y){table[++tot].to=y;table[tot].next=head[x];head[x]=tot;}void DFS(int x){[M],top;int i,bottom=top;dpt[x]=dpt[fa[x]]+1;for(i=1;i<=15;i++)ancestor[x][i]=ancestor[ancestor[x][i-1]][i-1];for(i=head[x];i;i=table[i].next)if(table[i].to!=fa[x]){fa[table[i].to]=ancestor[table[i].to][0]=x;DFS(table[i].to);if(top-bottom>=b1){++_cnt;while(top>bottom)belong[stack[top–]]=_cnt;}}stack[++top]=x;if(x==1){++_cnt;while(top)belong[stack[top–]]=_cnt;}}void Update(int x){v[x]=true;if(a[x]>n) return ;cnt[a[x]]++;if(cnt[a[x]]==1)block[a[x]/b2]++;}void Downdate(int x){v[x]=false;if(a[x]>n) return;cnt[a[x]]–;if(!cnt[a[x]])block[a[x]/b2]–;}int LCA(int x,int y){int j;if(dpt[x]<dpt[y])swap(x,y);for(j=15;~j;j–)if(dpt[ancestor[x][j]]>=dpt[y])x=ancestor[x][j];if(x==y) return x;for(j=15;~j;j–)if(ancestor[x][j]!=ancestor[y][j])x=ancestor[x][j],y=ancestor[y][j];return ancestor[x][0];}void Transfer(int x,int y){int lca=LCA(x,y);for(;x!=lca;x=fa[x]){if(v[x]) Downdate(x);else Update(x);}for(;y!=lca;y=fa[y]){if(v[y]) Downdate(y);else Update(y);}}int Get_Mex(){int i,j;for(i=0;;i++)if(block[i]!=b2)for(j=i*b2;;j++)if(!cnt[j])return j;}int main(){int i,p,x,y;cin>>n>>m;b1=pow(n,2.0/3.0)+1e-7;b2=sqrt(n)+1e-7;for(i=1;i<=n;i++)scanf(“%d”,&a[i]);for(i=1;i<n;i++){scanf(“%d%d”,&x,&y);Add(x,y);Add(y,x);}DFS(1);for(i=1;i<=m;i++){scanf(“%d%d%d”,&p,&x,&y);if(p==0){modifictions[++c].x=x;modifictions[ c].from=a[x];modifictions[ c].to=y;modifictions[ c].t=i;a[x]=y;}else{if(belong[x]>belong[y])swap(x,y);queries[++q].x=x;queries[ q].y=y;queries[ q].t=i;}}t=c;sort(queries+1,queries+q+1);for(i=1;i<=q;i++){int lca=LCA(queries[i].x,queries[i].y);Transfer(L,queries[i].x);Transfer(R,queries[i].y);L=queries[i].x;R=queries[i].y;while( modifictions[t].t > queries[i].t ){if(v[modifictions[t].x]){Downdate(modifictions[t].x);a[modifictions[t].x]=modifictions[t].from;Update(modifictions[t].x);}elsea[modifictions[t].x]=modifictions[t].from;–t;}while( t<c && modifictions[t+1].t < queries[i].t ){if(v[modifictions[t+1].x]){Downdate(modifictions[t+1].x);a[modifictions[t+1].x]=modifictions[t+1].to;Update(modifictions[t+1].x);}elsea[modifictions[t+1].x]=modifictions[t+1].to;++t;}Update(lca);queries[i].ans=Get_Mex();Downdate(lca);}sort(queries+1,queries+q+1,Compare);for(i=1;i<=q;i++)printf(“%d\n”,queries[i].ans);return 0;}
我们一直在旅行，一直在等待某个人可以成为我们旅途的伴侣，
