最大值最小，可以二分，然后并查集看能不能到z个点
但是询问过多，并且发现每次二分要加入的点并不是所有的m条边
于是就考虑整体二分
并查集的处理是重点：
对于一般的dfs分治树，
我们必然要在处理前面部分回溯来的时候，递归右子树之前，左子树并查集的信息必须保留。
但是还要删除当前层的部分并查集的合并操作。
如果直接路径压缩+暴力重构的话，到了后面，每次重构就是O(n)的了，直接N^2了。
为了支持删除，就考虑按秩合并。
合并成功的时候，用一个栈记录pair，然后删除的时候弹栈删除即可。相当于时光倒流
当然，之前的合并一定不能撤销的。
出错点：
1.l打成1海星。。。
2.如果当前区间没有决策位置的话，可以直接返回，但是这些[l,r]编号的边不能扔掉，必须直接加进去。
#include<bits/stdc++.h>
#define il inline
#define reg register int
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=1e5+;
const int M=1e5+;
struct node{
int x,y;
}e[M];
struct que{
int x1,x2,z;
int id,ans;
}q[M],b[M];
int fa[N];
int sz[N];
int op[N];
int n,m;
int fin(int x){
return fa[x]==x?x:fin(fa[x]);
}
pair<int,int>sta[N];
int top;
void merge(int x,int y,bool fl){
int k1=fin(x),k2=fin(y);
if(k1!=k2){
if(sz[k1]>sz[k2]) swap(k1,k2);
fa[k1]=k2;
sz[k2]+=sz[k1];
if(fl)sta[++top]=make_pair(k1,k2);
}
}
void dele(int x,int y){
fa[x]=x;
sz[y]-=sz[x];
}
void divi(int l,int r,int le,int ri){
//cout<<" l r "<<l<<" "<<r<<" : "<<le<<" and "<<ri<<endl;
if(l>r) return;
if(le>ri){
for(reg i=l;i<=r;++i){
merge(e[i].x,e[i].y,);
}
return;
}
if(l==r){
for(reg i=le;i<=ri;++i){
q[i].ans=l;
}
merge(e[l].x,e[l].y,);
return;
}
int mid=(l+r)>>;
for(reg i=l;i<=mid;++i){
merge(e[i].x,e[i].y,);
}
//cout<<" mid "<<mid<<endl;
int pre=le-,bac=ri+;
for(reg i=le;i<=ri;++i){
int k1=fin(q[i].x1),k2=fin(q[i].x2);
int tmp=;
if(k1!=k2){
tmp=sz[k1]+sz[k2];
}else{
tmp=sz[k1];
}
if(tmp>=q[i].z) b[++pre]=q[i];
else b[--bac]=q[i];
}
for(reg i=le;i<=ri;++i){
q[i]=b[i];
}
//cout<<" pre "<<pre<<" bac "<<bac<<" top "<<top<<endl;
//if(top){
while(top){
dele(sta[top].first,sta[top].second);
--top;
}
//}
divi(l,mid,le,pre);
divi(mid+,r,bac,ri);
}
int main(){
rd(n);rd(m);
for(reg i=;i<=m;++i){
rd(e[i].x);rd(e[i].y);
}
int que;
rd(que);
for(reg i=;i<=que;++i){
rd(q[i].x1);rd(q[i].x2);rd(q[i].z);
q[i].id=i;
}
for(reg i=;i<=n;++i){
fa[i]=i;sz[i]=;//;dep[i]=1;
}
divi(,m,,que);
for(reg i=;i<=que;++i){
op[q[i].id]=q[i].ans;
}
for(reg i=;i<=que;++i){
printf("%d\n",op[i]);
}
return ;
} }
signed main(){
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2018/12/18 8:37:44
*/
还有一种：
你不是暴力重构会TLE吗？但是我一共就需要循环logn次O(m)地把并查集加入
考虑逐层处理
因为对于整体二分，bfs和dfs的顺序都没有问题。
所以bfs处理整体二分，这样，加入就直接加入了，只要暴力重构O(logn)次。
bfs+路径压缩，理论上可以更快一些。