P11801 【MX-X9-T5】『GROI-R3』Star Trip sol

· · 题解

我永远喜欢 Neri 酱！

先考虑最优策略是什么：假设我们从点 s 出发，首先如果有一个与 s 相邻的 p 满足 p<s，则我们显然不增加答案就可以直接访问 p。不妨维护一个当前可以任意访问的连通块，则上面的操作就是直接把编号不超过 s 的相邻点并入连通块。

在所有这样的操作都做完后，与连通块相邻的所有点编号都大于 s。这时如果 t 已经在连通块中，则答案就是 1；否则我们令答案加一，并访问当前能访问的编号最大的点，这是因为我们的路径可以经过重复的点和边，访问完编号最大的点后原路返回一定也能访问其他的点。

这个过程看起来很能倍增，考虑求出以每个点为起点，其对应的连通块能到达的权值最大的点。我们按照编号从小到大的顺序求解，对当前点 x，遍历 x 的所有邻接点 y，如果 y<x，就与 y 所在连通块的答案取 \max，否则就与 y 取 \max。最后再合并 x 与小于 x 的 y 对应的连通块。

现在对于一个询问，我们就可以倍增得到 u 走若干步能到达的点编号的范围了，唯一的问题是：我们如何判断倍增后是否能到达 v？考虑求出所有 u 到 v 的路径中，最大点权的最小值，如果当前能访问的点权不小于这个值，则 v 已经在当前连通块中。我们令一条 (u,v) 边的权值为 \max(u,v)，则上面的问题等价于最小瓶颈路，建出 Kruskal 重构树后求 LCA 即可。

总复杂度 O(n\log n+q\log n)。

code :

#include<bits/stdc++.h>
using namespace std;
#define N    1000010
#define int  long long
#define pb   push_back
#define il   inline
il int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int T=1,n,m,q,k;
int s[N];
char c[N];
vector<int> v[N];
int w[N],ww[N];
int to[21][N];
struct node{
    int x,y,z;
}e[N];
il bool cmp(const node &a,const node &b){
    return a.z<b.z;
}
int tot,f[N];
il int fd(int x){
    if(x==f[x])return x;
    return f[x]=fd(f[x]);
}
int val[N];
vector<int> V[N];
il void link(int x,int y,int z){
    int a=fd(x),b=fd(y);
    if(a==b)return ;
    val[++tot]=z;
    f[a]=f[b]=tot;
    V[tot].pb(a),V[tot].pb(b);
}
int fa[21][N],dep[N];
il void dfs(int x){
    for(int i=1;i<=20;i++)
        fa[i][x]=fa[i-1][fa[i-1][x]];
    for(auto y:V[x]){
        fa[0][y]=x;
        dep[y]=dep[x]+1;
        dfs(y);
    }
}
il int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--)
        if(dep[fa[i][x]]>=dep[y])
            x=fa[i][x];
    if(x==y)return x;
    for(int i=20;i>=0;i--)
        if(fa[i][x]!=fa[i][y])
            x=fa[i][x],y=fa[i][y];
    return fa[0][x];
}
il void solve(){
    tot=n=read();m=read();q=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        e[i].x=x,e[i].y=y,e[i].z=max(x,y);
        v[x].pb(y),v[y].pb(x);
    }
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=n*2;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        link(e[i].x,e[i].y,e[i].z);
    }
    dfs(tot);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=n;i++)w[i]=i;
    for(int x=1;x<=n;x++){
        for(auto y:v[x]){
            if(y<x)w[x]=max(w[x],ww[fd(y)]);
            else w[x]=max(w[x],y);
        }
        ww[x]=w[x];
        for(auto y:v[x]){
            if(y<x){
                int a=fd(x),b=fd(y);
                if(a==b)continue;
                ww[b]=max(ww[b],ww[a]);
                f[a]=b;
            }
        }
    }
    for(int i=1;i<=n;i++)to[0][i]=w[i];
    for(int k=1;k<=20;k++)for(int i=1;i<=n;i++)to[k][i]=to[k-1][to[k-1][i]];
    while(q--){
        int x=read(),y=read();
        int aaa=val[lca(x,y)];
        if(x>=aaa){
            puts("1");
            continue;
        }
        int sum=0;
        for(int k=20;k>=0;k--)
            if(to[k][x]<aaa){
                sum+=(1<<k);
                x=to[k][x];
            }
        printf("%lld\n",sum+2);
    }
}
signed main(){
    T=1;
    while(T--)solve();
    return 0;
}