AGC002D Stamp Rally

Description

给定一张个点条边的无向连通图，每条边的边权是它的编号。

次询问，每次询问给定，表示询问从出发，恰好经过个点后经过边权最大值的最小值。

Sol

“恰好”看似唬人实则是噱头，因为只要能到达个点那么就一定能恰好到达个点。

然后分析得出只有最小生成树上的边才有用（走最小生成树一定不劣）。

这里就可以考虑两种做法：

整体二分

答案显然满足单调性，考虑二分。

但是分别二分是非常爆炸级别的。

考虑离线下来做整体二分，二分为加入之后是否满足答案。

我们发现我们需要实时维护所在连通块大小，并且要支持查询历史版本，那么Kruskal的时候开一个可持久化并查集记录连通块大小即可。

时间复杂度。

Kruskal重构树

如果不会，请求助谷歌娘或度娘。

Kruskal重构树有一个很好的性质：如果结点编号边编号，从叶结点到根的结点编号是递增的。

这意味着我们可以在二分答案的时候在重构树上倍增计算最远能跳到的位置（只需要判断子树叶结点个数），这样单次二分时间复杂度降到了，可以接受。

时间复杂度。

Code

下面的代码为Kruskal重构树。

#include<bits/stdc++.h>
const int M=1e6+5;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}

struct edge{
    int u,v;
}e[M];
int n,m;
std::vector<int> G[M];
int fa[M][21],siz[M];
void adde(int u,int v){G[u].push_back(v);fa[v][0]=u;}
int ufs[M];
int ff(int x){return ufs[x]==x?x:ufs[x]=ff(ufs[x]);}
bool mrg(int u,int v){
    u=ff(u),v=ff(v);
    return u==v?0:ufs[u]=v,1;
}
void dfs(int u){
    if(u<=n)siz[u]=1;
    for(int i=1;i<=20;++i)fa[u][i]=fa[fa[u][i-1]][i-1];
    for(auto v:G[u])dfs(v),siz[u]+=siz[v];
}
void build(){
    for(int i=1;i<=n+m;++i)ufs[i]=i;
    for(int i=1,tot=0;i<=m;++i){
        int u=e[i].u,v=e[i].v;
        int uu=ff(u),vv=ff(v);
        if(uu==vv)continue;
        adde(i+n,uu),adde(i+n,vv);
        ufs[uu]=i+n,ufs[vv]=i+n;
        ++tot;
        if(tot==n-1){
            for(int j=0;j<=20;++j)fa[i+n][j]=i+n;
            dfs(i+n);
            return;
        }
    }
}
bool chk(int u,int v,int mid,int w){
    for(int i=20;i>=0;--i){
        if(fa[u][i]<=mid)u=fa[u][i];
        if(fa[v][i]<=mid)v=fa[v][i];
    }
    int res=0;
    if(u==v)res=siz[u];
    else res=siz[u]+siz[v];
    return res>=w;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        e[i]=(edge){u,v};
    }
    build();
    int q=read();
    while(q--){
        int u=read(),v=read(),w=read();
        int l=0,r=m;
        while(l<r){
            int mid=(l+r)>>1;
            if(chk(u,v,mid+n,w))r=mid;
            else l=mid+1;
        }
        printf("%d\n",l);
    }
    return 0;
}