本题解用于作者加深算法印象，也欢迎各位的阅读。
给你一张无向图，并给你两种操作：
\(1~v\) ：找到当前点 \(v\) 所在的联通块内权值最大的点，输出该点权值并将其权值改为 \(0\) 。
\(2~i\) ：删去编号为 \(i\) 的边。
然后你发现这个东西不是很好搞，但是这里提供了一个很好的维护联通块的东西——\(Kruskal\) 重构树。
我们可以将每条边删去的时间戳记为这条边的权值，可以轻易的发现，如果我们将边权从大到小（即在时间上从后往前）建起 \(Kruskal\) 重构树的话，每个子树都代表着一个时间点上的联通块，我们只需要对这个子树做我们的 \(1\) 操作就可以了，这个可以用 \(dfs\) 序加线段树来实现，这里就不多赘述了。
以上。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=3e5+5,Q=5e5+5;
int n,m,q,a[N<<1],b[N<<1];
struct Edge{int u,v,w,tag;}e[M];
bool cmp(Edge a,Edge b){return a.tag>b.tag;}
struct operation{int opt,x;}s[Q];
struct Seg_Tree
{
struct Node{int data,pos;}tr[N<<4];
void up(int u)
{
if(tr[u<<1].data>tr[u<<1|1].data) tr[u]=tr[u<<1];
else tr[u]=tr[u<<1|1];
}
void build(int u,int l,int r,int a[])
{
if(l==r){tr[u].data=a[l],tr[u].pos=l;return;}
int mid=(l+r)>>1;
build(u<<1,l,mid,a),build(u<<1|1,mid+1,r,a);
up(u);
}
int query(int u,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return u;
int mid=(l+r)>>1,res=0,tmp;
if(x<=mid)
{
tmp=query(u<<1,l,mid,x,y);
if(tr[res].data<=tr[tmp].data) res=tmp;
}
if(y>mid)
{
tmp=query(u<<1|1,mid+1,r,x,y);
if(tr[res].data<=tr[tmp].data) res=tmp;
}
return res;
}
void del(int u,int l,int r,int x)
{
if(x<=l&&r<=x){tr[u].data=0;return;}
int mid=(l+r)>>1;
if(x<=mid) del(u<<1,l,mid,x);
else del(u<<1|1,mid+1,r,x);
up(u);
}
}Seg;
struct Kruskal_Tree
{
int size;
struct DSU
{
int fa[N<<1];
void init(){for(int i=1;i<(N<<1);++i)fa[i]=i;}
int find(int x){if(fa[x]!=x)fa[x]=find(fa[x]);return fa[x];}
}d;
struct Edge{int nxt,to;}e[N<<1];
int fir[N<<1],e_size;
void add(int u,int v){e[++e_size]=Edge{fir[u],v},fir[u]=e_size;}
struct Node{int fa[22],dep,data,mp;}tr[N<<1];
int dfn[N<<1],l[N<<1],r[N<<1],dfn_num;
void dfs(int u)
{
dfn[++dfn_num]=u,tr[u].mp=dfn_num;
l[u]=dfn_num;
// printf("%d %d\n",u,tr[u].data);
for(int i=fir[u];i;i=e[i].nxt)
{
tr[e[i].to].fa[0]=u;
tr[e[i].to].dep=tr[u].dep+1;
dfs(e[i].to);
}
r[u]=dfn_num;
}
int lca(int u,int v)
{
if(tr[u].dep<tr[v].dep) swap(u,v);
for(int i=20;i>=0;--i)
{
if(tr[tr[u].fa[i]].dep>=tr[v].dep)
u=tr[u].fa[i];
}
if(u==v) return u;
for(int i=20;i>=0;--i)
{
if(tr[u].fa[i]!=tr[v].fa[i])
u=tr[u].fa[i],v=tr[v].fa[i];
}
return tr[u].fa[0];
}
}t;
int main()
{
cin>>n>>m>>q;
t.size=n,t.d.init();
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=m;++i) scanf("%d%d",&e[i].u,&e[i].v),e[i].tag=q+1;
// printf("\n----------------\n");
for(int i=1;i<=q;++i)
{
scanf("%d%d",&s[i].opt,&s[i].x);
if(s[i].opt==2) e[s[i].x].tag=i;
}
sort(e+1,e+1+m,cmp);
for(int i=1;i<=m;++i)
{
int fu=t.d.find(e[i].u);
int fv=t.d.find(e[i].v);
if(fu==fv) continue;
t.tr[++t.size].data=e[i].tag;
t.add(t.size,fu),t.add(t.size,fv);
// printf("%d %d %d\n",t.size,fu,fv);
t.d.fa[fu]=t.d.fa[fv]=t.size;
}
for(int i=1;i<=t.size;++i)
{
int tmp=t.d.find(i);
if(t.tr[tmp].mp) continue;
t.tr[tmp].dep=1;
t.dfs(tmp);
}
// for(int i=1;i<=t.size;++i)
// {
// printf("%d %d %d\n",t.tr[i].fa[0],t.tr[i].dep,t.tr[i].data);
// }
for(int i=1;i<=20;++i)
{
for(int j=1;j<=t.size;++j)
t.tr[j].fa[i]=t.tr[t.tr[j].fa[i-1]].fa[i-1];
}
for(int i=1;i<=t.size;++i) b[i]=a[t.dfn[i]];
Seg.build(1,1,t.size,b);
for(int i=1;i<=q;++i)
{
if(s[i].opt==2) continue;
int tmp=s[i].x;
for(int j=20;j>=0;--j)
{
if(t.tr[t.tr[tmp].fa[j]].data>i)
tmp=t.tr[tmp].fa[j];
}
tmp=Seg.query(1,1,t.size,t.l[tmp],t.r[tmp]);
// printf("%d %d ",tmp,Seg.tr[tmp].pos);
printf("%d\n",Seg.tr[tmp].data);
Seg.del(1,1,t.size,Seg.tr[tmp].pos);
}
}
题解 CF1416D 【Graph and Queries】
原文：https://www.cnblogs.com/Point-King/p/13752806.html