[AGC002D] Stamp Rally 整体二分+并查集

Description

给你一个n个点m个条边构成的简单无向连通图，有Q组询问，每次询问从两个点x,y走出两条路径，使这两条路径覆盖z个点，求得一种方案使得路径上经过的变的最大编号最小。

Input

第一行两个整数n,m，如题目所述

接下来m行，每行两个整数x,y描述一条边

接下来一个整数Q，如题目所述

接下来Q行，每行三个整数x,y,z，如题目描述

Output

Q行，每行一个正整数，如题目描述

Sample Input

5 6
2 3
4 5
1 2
1 3
1 4
1 5
6
2 4 3
2 4 4
2 4 5
1 3 3
1 3 4
1 3 5

Sample Output

1
2
3
1
5
5

HINT

n,m,q≤10^5

Sol

考虑单组询问的做法，显然可以二分答案，然后用并查集把所有小于等于的边合并，判断是否可行即可。

这里每组询问互相独立，我们上整体二分即可。

如果把整体二分写成BFS形式的话不用还原并查集啦，而且好写得多，具体地，我们建出类似线段树的东西，然后求出每个线段的mid，按照顺序并查集合并，如果当前i和这一层其中一个mid相等就判断这个节点vector中的元素是否达标并下传即可。

每一层要清空并查集。

Code

#include <bits/stdc++.h>
using namespace std;
struct que{int x,y,z;}q[100005];vector<int>v[800050];
int n,m,Q,x,y,now=1,U[100005],V[100005],cnt[100005],ans[100005],mid[800050],l[800050],r[800050],f[100005],sz[100005];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void bud(int x,int L,int R){l[x]=L;r[x]=R;mid[x]=(L+R)>>1;if(L==R) return;bud(x*2,L,mid[x]);bud(x*2+1,mid[x]+1,R);}
int main()
{
    scanf("%d%d",&n,&m);memset(ans,0x3f,sizeof(ans));
    for(int i=1;i<=m;i++) scanf("%d%d",&x,&y),U[i]=x,V[i]=y;
    scanf("%d",&Q);bud(1,1,m);
    for(int i=1;i<=Q;i++) scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z),v[1].push_back(i);
    for(int gg=m*4;gg;gg>>=1)
    {
        for(int i=1;i<=n;i++) f[i]=i,sz[i]=1,cnt[i]=0;
        for(int i=1;i<=m;i++)
        {
            if((x=find(V[i]))!=(y=find(U[i]))) f[y]=f[x],sz[x]+=sz[y];
            if(i==mid[now]) for(int j=0;j<v[now].size();j++)
            {
                int a=find(q[v[now][j]].x),b=find(q[v[now][j]].y);
                cnt[v[now][j]]=(a==b)?sz[a]:sz[a]+sz[b];
                if(cnt[v[now][j]]<q[v[now][j]].z) v[now*2+1].push_back(v[now][j]);
                else v[now*2].push_back(v[now][j]),ans[v[now][j]]=mid[now];
            }
            if(i==mid[now]||!mid[now]) now++;
        }
    }
    for(int i=1;i<=Q;i++) printf("%d
",ans[i]);
}