【AtCoder1998】Stamp Rally（整体二分+并查集）

题意

我们有一个N (3<=N<=10^5)个结点和M(N−1≤M≤10^5)个边的无向图。 结点编号为1到N，边编号为1到M。边i连接结点ai和bi。保证图连通。在这张图上，Q(1≤Q≤10^5)对兄弟正在参加一项名为Stamp Rally的活动。 第i对Stamp Rally如下：
一个兄弟从结点xi开始，另一个从结点yi开始。(1≤xi < yi≤N)
两个兄弟沿着边访问图上的结点，总共访问zi(3≤zi≤N)个结点，包括起始结点。 在这里，即使一个结点被多次访问，只计算一次。
定义得分为它们走过的边的最大编号。 他们的目标是尽量减少这个得分。
找出每对兄弟的最低分数。

题解

以边的编号从小到大加入图中，利用并查集，每加入一条边i，扫描所有询问，如果他们所在联通快大小达到了zi，则这个询问的答案 为i。
但这样是$O(MQ)$的。
利用整体二分，先加入前面一半$[l,mid]$的边，判断哪些询问已经达到条件，则这些询问的答案一定$\leq mid$，将其划分到前面一半，然后将并查集复原，递归处理$[l,mid]$的询问，和$[mid+1,r]$的询问。
为了使并查集复原，可使用按秩合并。

代码

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=100005;

int N,M,Q;

struct Edge
{
    int u,v;
}E[MAXN];
struct Query
{
    int x,y,z;
}q[MAXN];
int id[MAXN],tmp[MAXN],mk[MAXN],ans[MAXN];

int stk[MAXN][2],tp;
int fa[MAXN],siz[MAXN];
int Root(int u)
{
    if(fa[u]==0)
        return u;
    return Root(fa[u]);
}
void Union(int u,int v)
{
    int r1=Root(u),r2=Root(v);
    if(r1==r2)
        return;
    if(siz[r1]<siz[r2])
        swap(r1,r2);
    fa[r2]=r1;
    stk[++tp][0]=r2;
    stk[tp][1]=r1;
    siz[r1]+=siz[r2];
}

void solve(int a,int b,int l,int r)
{
    if(a==b)
    {
        for(int i=l;i<=r;i++)
            ans[id[i]]=a;
        Union(E[a].u,E[a].v);
        return;
    }
    tp=0;
    int mid1=(a+b)/2;
    for(int i=a;i<=mid1;i++)
        Union(E[i].u,E[i].v);
    for(int i=l;i<=r;i++)
    {
        int r1=Root(q[id[i]].x),r2=Root(q[id[i]].y);
        if(r1==r2&&siz[r1]>=q[id[i]].z)
            mk[i]=1;
        if(r1!=r2&&siz[r1]+siz[r2]>=q[id[i]].z)
            mk[i]=1;
    }
    int it=l-1;
    for(int i=l;i<=r;i++)
        if(mk[i])
            tmp[++it]=id[i];
    int mid2=it;
    for(int i=l;i<=r;i++)
        if(!mk[i])
            tmp[++it]=id[i];
    for(int i=l;i<=r;i++)
        id[i]=tmp[i],mk[i]=0;
    while(tp)
    {
        fa[stk[tp][0]]=0;
        siz[stk[tp][1]]-=siz[stk[tp][0]];
        tp--;
    }
    solve(a,mid1,l,mid2);
    solve(mid1+1,b,mid2+1,r);
}

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
        scanf("%d%d",&E[i].u,&E[i].v);
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++)
        scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);
    for(int i=1;i<=N;i++)
        fa[i]=0,siz[i]=1;
    for(int i=1;i<=Q;i++)
        id[i]=i;
    solve(1,M,1,Q);
    for(int i=1;i<=Q;i++)
        printf("%d\n",ans[i]);

    return 0;
}