[agc002d]Stamp Rally

前言

简单套路题。

题目大意

一副连通图，每次询问从两个点x和y出发走出两条路径，希望至少经过一次的点数量等于z，经过的边最大编号最小是多少。

简单题

假如可以暴力，你可以按编号从小到大加入边，如果x和y不在一个联通块，能经过的点等于两个所在联通块大小的和，否则等于所在联通块大小，找到第一次大于等于z的位置。
不枚举也可以二分。
那不如整体二分吧，并查集采用按秩合并，好处是容易撤销。

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=100000+10;
int a[maxn][2],ask[maxn][3],b[maxn],c[maxn],ans[maxn];
bool bz[maxn];
int fa[maxn],size[maxn],sta[maxn][2];
int i,j,k,l,t,n,m,q,top,tot;
int getfa(int x){
    return fa[x]?/*fa[x]=*/getfa(fa[x]):x;
}
void solve(int l,int r,int u,int v){
    int i,j,k,t;
    if (l==r){
        fo(i,u,v) ans[b[i]]=l;
        j=a[l][0];k=a[l][1];
        j=getfa(j);k=getfa(k);
        if (size[j]>size[k]) swap(j,k);
        if (j!=k){
            fa[j]=k;
            size[k]+=size[j];
        }
        return;
    }
    int mid=(l+r)/2;
    top=0;
    fo(i,l,mid){
        j=a[i][0];k=a[i][1];
        j=getfa(j);k=getfa(k);
        if (size[j]>size[k]) swap(j,k);
        if (j!=k){
            fa[j]=k;
            size[k]+=size[j];
            sta[++top][0]=j;
            sta[top][1]=k;
        }
    }
    fo(i,u,v) bz[i]=0;
    fo(i,u,v){
        j=ask[b[i]][0];k=ask[b[i]][1];
        j=getfa(j);k=getfa(k);
        if (j==k&&size[j]>=ask[b[i]][2]) bz[i]=1;
        else if (j!=k&&size[j]+size[k]>=ask[b[i]][2]) bz[i]=1;
    }
    tot=u-1;
    fo(i,u,v)
        if (bz[i]) c[++tot]=b[i];
    t=tot;
    fo(i,u,v)
        if (!bz[i]) c[++tot]=b[i];
    fo(i,u,v) b[i]=c[i];
    while (top){
        j=sta[top][0];k=sta[top][1];
        fa[j]=0;
        size[k]-=size[j];
        top--;
    }
    solve(l,mid,u,t);
    solve(mid+1,r,t+1,v);
}
int main(){
    scanf("%d%d",&n,&m);
    fo(i,1,m) scanf("%d%d",&a[i][0],&a[i][1]);
    scanf("%d",&q);
    fo(i,1,q) scanf("%d%d%d",&ask[i][0],&ask[i][1],&ask[i][2]);
    fo(i,1,q) b[i]=i;
    fo(i,1,n) size[i]=1;
    solve(1,m,1,q);
    fo(i,1,q) printf("%d\n",ans[i]);
}