整体二分板题
首先瑞平翻译。
考虑整体二分，用分治函数 solve(l,r,L,R) 解决答案在 \([L,R]\) 之间的边。每次我们加入所有 \([1,MID]\) 之间的边，查询这时的询问是否满足要求，进行整体二分即可。
由于多次加入边比较麻烦，我们用可撤销并查集维护。
时间复杂度 \(O(n \log^2 n)\)
code:
#include<bits/stdc++.h>
using namespace std;
const int MX=1e5+7;
int fa[MX],sz[MX];
struct info{
int fa,sz,x,y;
}stk[MX];
int top=0;
long long cnt = 0;
int find(int x){
++cnt;
while(fa[x]!=x)x=fa[x], ++cnt;
return x;
}
void merge(int x,int y){
int xx=find(x),yy=find(y);
if(xx==yy){
stk[++top]=(info){-1,-1,-1,-1};
return ;
}
if(sz[xx]>sz[yy])swap(xx,yy);
stk[++top]=(info){fa[xx],sz[yy],xx,yy};
fa[xx]=yy;
sz[yy]+=sz[xx];
}
void reroll(){
info tmp=stk[top];
if(tmp.x!=-1){
fa[tmp.x]=tmp.fa;
sz[tmp.y]=tmp.sz;
}
top--;
}
struct query{
int x,y,z,ans,t;
}qu[MX];
struct edge{
int u,v;
}e[MX];
bool cmp(query x,query y){
return x.t<y.t;
}
bool check(query x){
int xx=find(x.x),yy=find(x.y);
if(xx==yy)return sz[xx]>=x.z;
return sz[xx]+sz[yy]>=x.z;
}
int sum=0;
void solve(int l,int r,int L,int R){
if(l>r||L>=R)return;
int MID=L+R>>1;
sum+=R-MID+1;
for(int i=MID+1;i<=R;i++)reroll();
int t=l-1;
for(int i=l;i<=r;i++){
if(check(qu[i])){
qu[i].ans=MID;
swap(qu[i],qu[++t]);
}
else qu[i].ans=MID+1;
}
solve(l,t,L,MID);
for(int i=MID+1;i<=R;i++)merge(e[i].u,e[i].v);
solve(t+1,r,MID+1,R);
}
int main(){
ios::sync_with_stdio(false);
int n,m,q;
cin>>n>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
sz[i]=1;
}
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v;
merge(e[i].u,e[i].v);
}
cin>>q;
for(int i=1;i<=q;i++){
cin>>qu[i].x>>qu[i].y>>qu[i].z;
qu[i].t=i;
}
solve(1,q,1,m);
sort(qu+1,qu+1+q,cmp);
//cout<<sum<<endl;
for(int i=1;i<=q;i++)cout<<qu[i].ans<<endl;
//cerr << "cnt = " << cnt << endl;
return 0;
}