题意：
给出一个无向图，Q次询问，每次询问给出两个点(x,y)，求包含x，y的总大小不低于z的联通块（可能x，y不在一个联通块中），使得联通块中的边的序号最大值尽可能小。
分析：
好久没写整体二分了。。。
这里顺便复习一下：
对询问和答案同时二分，每次判断答案中间值后，把询问归为左右两类，使得每一层的时间复杂度均摊下来是O(n)级别的。
检查用并查集就行了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
struct Query{int id;int x,y,sz;
}que[MAXN],tmp[MAXN];
pair<int,int> link[MAXN];
int ans[MAXN];
int fa[22][MAXN],siz[22][MAXN];
int get_fa(int dep,int x){if(fa[dep][x]==0)return x;fa[dep][x]=get_fa(dep,fa[dep][x]);return fa[dep][x];
}
void add_edge(int l,int r,int dep){for(int i=l;i<=r;i++){int u=get_fa(dep,link[i].first);int v=get_fa(dep,link[i].second);if(u!=v){fa[dep][u]=v;siz[dep][v]+=siz[dep][u]; }}
}
int count(int dep,int x,int y,int sz){x=get_fa(dep,x);y=get_fa(dep,y);if(x==y)return siz[dep][x]>=sz;elsereturn (siz[dep][x]+siz[dep][y])>=sz;
}
void Solve(int l,int r,int ql,int qr,int dep){if(l==r){for(int i=ql;i<=qr;i++)ans[que[i].id]=l;add_edge(l,r,dep);return ; }int mid=(l+r)>>1;add_edge(l,mid,dep);int tl=ql,tr=qr;for(int i=ql;i<=qr;i++){if(count(dep,que[i].x,que[i].y,que[i].sz)==1)tmp[tl++]=que[i];elsetmp[tr--]=que[i];}for(int i=ql;i<=qr;i++)que[i]=tmp[i];add_edge(mid+1,r,dep);Solve(l,mid,ql,tr,dep+1);Solve(mid+1,r,tl,qr,dep+1);
}
int main(){int n,m,q;SF("%d%d",&n,&m);for(int i=0;i<20;i++)for(int j=1;j<=n;j++)siz[i][j]=1;for(int i=1;i<=m;i++)SF("%d%d",&link[i].first,&link[i].second);SF("%d",&q);for(int i=1;i<=q;i++){SF("%d%d%d",&que[i].x,&que[i].y,&que[i].sz);que[i].id=i;}Solve(1,m,1,q,0);for(int i=1;i<=q;i++)PF("%d\n",ans[i]);
}