道理我都懂，可是看了一眼其他题解为什么那么长啊。。。
#include<bits/stdc++.h> #define N 100100 using namespace std; struct Node{int x,y,z,l,r,las,ord;}q[N]; int n,m,Q; int fa[N],siz[N],ans[N]; int a[N],b[N]; int find_fa(int a){ return fa[a]==a?a:fa[a]=find_fa(fa[a]); } int main(){ scanf("%d%d",&n,&m); for(int i=0;i<m;i++) scanf("%d%d",&a[i],&b[i]); scanf("%d",&Q); for(int i=0,x,y,z;i<Q;i++){ scanf("%d%d%d",&x,&y,&z); q[i]=(Node){x,y,z,0,m-1,m,i}; } for(int l=0;m>>l;l++){ for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1; int sl=-1,sr=-1,use=0,beg=0,i=0,fal,far; for(int j=0;j<Q;j++){ if(q[j].l!=sl||q[j].r!=sr) beg=j,sl=q[j].l,sr=q[j].r; int mid=q[j].l+q[j].r+1>>1; while(i<mid&&i+1<m){ fal=find_fa(a[i]),far=find_fa(b[i]); if(fal!=far) siz[far]+=siz[fa[fal]],fa[fal]=far; i++; } fal=find_fa(q[j].x),far=find_fa(q[j].y); if(siz[fal]+siz[far]-(fal==far)*siz[fal]>=q[j].z){ q[j].r=mid-1,q[j].las=mid; swap(q[j],q[beg++]); } else q[j].l=mid+1; } } for(int i=0;i<Q;i++) ans[q[i].ord]=q[i].las; for(int i=0;i<Q;i++) printf("%d\n",ans[i]); return 0; }