传送门

裸的整体二分+可持久化并查集。

直到现在才彻底搞清楚可持久化并查集的时间戳到底是怎么打的。。。我好菜啊。。。

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#define MAXN 100010
using namespace std;

int n,m,numq;
int e[MAXN][2];
int f[MAXN],rk[MAXN],tf[MAXN];
vector< pair<int,int> > size[MAXN];
int ans[MAXN];

struct Query{
    int x1,x2,k,id;
}q[MAXN],q0[MAXN];

int getf(int x,int t){
    while(x!=f[x] && tf[x]<=t) x=f[x];
    return x;
}

int getsize(int x,int t){
    int l=0,r=size[x].size()-1;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(size[x][mid].first<=t) l=mid;
        else r=mid-1;
    }
    return size[x][l].second;
}

void build(){
    for(int i=1;i<=n;i++){
        f[i]=i;
        size[i].push_back(make_pair(0,1));
    }
    for(int i=1;i<=m;i++){
        int x=getf(e[i][0],m),y=getf(e[i][1],m);
        if(x==y) continue;
        if(rk[x]<rk[y]) x^=y^=x^=y;
        f[y]=x;
        tf[y]=i;
        if(rk[x]==rk[y]) rk[x]++;
        size[x].push_back(make_pair(i,size[x][size[x].size()-1].second+size[y][size[y].size()-1].second));
    }
}

void solve(int l,int r,int ql,int qr){
    if(ql>qr) return;
    if(l==r){
        for(int i=ql;i<=qr;i++)
            ans[q[i].id]=l;
        return;
    }
    int mid=(l+r)>>1;
    for(int i=ql;i<=qr;i++) q0[i]=q[i];
    int now1=ql-1,now2=qr+1;
    for(int i=ql;i<=qr;i++){
        int x1=q0[i].x1,x2=q0[i].x2,k=q0[i].k;
        x1=getf(x1,mid); x2=getf(x2,mid);
        int res=getsize(x1,mid);
        if(x1!=x2) res+=getsize(x2,mid);
        if(res>=k) q[++now1]=q0[i];
        else q[--now2]=q0[i];
    }
    solve(l,mid,ql,now1);
    solve(mid+1,r,now2,qr);
}

int main(){
#ifdef DEBUG
    freopen("D.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&e[i][0],&e[i][1]);
    scanf("%d",&numq);
    for(int i=1;i<=numq;i++){
        scanf("%d%d%d",&q[i].x1,&q[i].x2,&q[i].k);
        q[i].id=i;
    }
    build();
    solve(1,m,1,numq);
    for(int i=1;i<=numq;i++)
        printf("%d\n",ans[i]);
    return 0;
}