思路： 删边可以倒着来看就变成加边，维护一个可撤销并查集的同时对每个点维护一个set来储存p值，那么询问就是询问一个联通块中最大的p，我们在合并的时候用启发式合并的思想对两个set进行合并即可。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 5e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; int n,m,q,a[N]; vector<int>v[N]; struct uzi{ int x,y; bool operator <(const uzi & t)const{ return y>t.y; } }p[N]; int op[N],po[N],del[N],f[N],sz[N]; int find(int x){ while(x!=f[x]){ x=f[x]; } return x; } int st[N],tot; set<uzi>G[N]; void merge(int x,int y){ int dx=find(x),dy=find(y); if(dx==dy) return; if(sz[dx]>sz[dy])swap(dx,dy); sz[dy]+=sz[dx]; f[dx]=dy; st[++tot]=dx; for(auto k:G[dx]){ G[dy].insert(k); } } int nxt[N]; void er(int y){ while(tot>y){ int now=st[tot--]; sz[f[now]]-=sz[now]; for(auto k:G[now])if(G[f[now]].find(k)!=G[f[now]].end())G[f[now]].erase(k); f[now]=now; } } int main() { ios::sync_with_stdio(false); cin>>n>>m>>q; for(int i=1;i<=n;i++)cin>>a[i],f[i]=i,sz[i]=1,G[i].insert({i,a[i]}); for(int i=1;i<=m;i++){ int s,t; cin>>s>>t; p[i]={s,t}; } for(int i=1;i<=q;i++){ cin>>op[i]>>po[i]; if(op[i]==2)del[po[i]]=1; } for(int i=1;i<=m;i++){ if(!del[i])merge(p[i].x,p[i].y); } nxt[q+1]=tot; for(int i=q;i>=1;i--){ nxt[i]=nxt[i+1]; if(op[i]==2)merge(p[po[i]].x,p[po[i]].y),nxt[i]=tot; } for(int i=1;i<=q;i++){ if(op[i]==2)er(nxt[i+1]); else{ int now=po[i]; int x=find(now); //cout<<i<<' '<<now<<' '<<x<<' '<<sz[x]<<endl; while(!G[x].empty()&&!a[(*G[x].begin()).x])G[x].erase(G[x].begin()); if(G[x].empty())cout<<0<<'\n'; else{ cout<<a[(*G[x].begin()).x]<<'\n'; a[(*G[x].begin()).x]=0; } } } return 0; }