思路：反向并查集 + d f s +dfs +dfs序 + + +线段树
对询问进行离线操作，从后往前，最开始建立一张删除所有询问边后的图，然后倒着重构图，如果是操作一就更新查询结点为其祖先结点： Q [ i ] . s e = f i n d ( Q [ i ] . s e ) Q[i].se=find(Q[i].se) Q[i].se=find(Q[i].se)
如果是操作二就利用并查集建立新结点连边，具体就是新建立一个结点其儿子为这条边的两个结点，父亲也同时更新为该新结点。
然后对图跑 d f s dfs dfs序，然后转换为线段树求区间最值问题。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second #define pb push_back #define il inline int n,m,q,cnt; int a[N],f[N],in[N],out[N],pos[N],del[N]; PII edge[N],Q[N]; int find(int x){return x==f[x]?x:f[x]=find(f[x]);} vector<int>g[N]; struct node{ int l,r,mx; }tr[N<<2]; void Merge(int x,int y){ x=find(x),y=find(y); if(x==y) return; n++;f[n]=n,f[x]=f[y]=n; g[n].pb(x),g[n].pb(y); } void dfs(int u){ in[u]=++cnt; for(int v:g[u]) if(!in[v]) dfs(v); out[u]=cnt; } void re(int x){ tr[x].mx=max(tr[lx].mx,tr[rx].mx); } void build(int x,int l,int r){ tr[x].l=l,tr[x].r=r,tr[x].mx=0; if(l==r){ return; } int mid=(l+r)>>1; build(lx,l,mid); build(rx,mid+1,r); } void upd(int x,int p,int val){ if(tr[x].l==tr[x].r){ tr[x].mx=val;return; } int mid=(tr[x].l+tr[x].r)>>1; if(p<=mid) upd(lx,p,val); else upd(rx,p,val); re(x); } int que(int x,int l,int r){ if(tr[x].l>=l&&tr[x].r<=r) return tr[x].mx; int ans=0,mid=(tr[x].l+tr[x].r)>>1; if(l<=mid) ans=max(ans,que(lx,l,r)); if(r>mid) ans=max(ans,que(rx,l,r)); return ans; } int main(){ scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++){ scanf("%d",&a[i]),pos[a[i]]=i,f[i]=i; } for(int i=1;i<=m;i++) scanf("%d%d",&edge[i].fi,&edge[i].se); for(int i=1;i<=q;i++){ scanf("%d%d",&Q[i].fi,&Q[i].se); if(Q[i].fi==2) del[Q[i].se]=1; } for(int i=1;i<=m;i++) if(!del[i]) Merge(edge[i].fi,edge[i].se); for(int i=q;i;i--){ if(Q[i].fi==1) Q[i].se=find(Q[i].se); else Merge(edge[Q[i].se].fi,edge[Q[i].se].se); } for(int i=1;i<=n;i++) if(f[i]==i) dfs(i); build(1,1,n); for(int i=1;i<=n;i++) upd(1,in[i],a[i]); for(int i=1;i<=q;i++){ if(Q[i].fi==1){ int ans=que(1,in[Q[i].se],out[Q[i].se]); printf("%d\n",ans); if(ans) upd(1,in[pos[ans]],0); } } return 0; }