题解：P11801 【MX-X9-T5】『GROI-R3』Star Trip

· · 题解

考场的思路，赛后的代码呃呃。

因为不会实现。

看到这道题，一下就想到的是当前点，如果必须花费 1 的代价，一定走到能到的最大点。

就是说，由 x，只走 \le x 的点，能到的所有点中相邻点的最大值，记为 ex_x。

考虑询问，每次花费 1 的代价跳到 ex_x。显然可以倍增优化。

这里的实现难点在如何求 ex_x 与如何判断退出，这也是我场上没想到的。

赛时主要卡在怎么判断当前能不能走到 t。每次跳完动态判连通肯定不行，但反过来考虑：什么时候可以不花代价直接走到 t？

显然就是存在一条 s 到 t 的路径，使得路径上所有点的编号都不超过当前的最大值。换句话说，我们要找一条路径，使得路径上的最大点权最小。

这本质是求 s 到 t 的最小瓶颈路 lim。

一条边 (u, v) 能走，至少需要点权限制达到 \max(u, v)。所以直接给每条边赋权 \max(u, v) 建出 Kruskal 重构树，到 lca(u , v) 的路径边权最大值即为 lim。

那么如果当前跳到的点 x \ge lim，显然 s 和 t 就已经连通了，直接退出即可。

然后求 ex_i，同样考虑 Kruskal 的思想。按点权从小到大加点，把 i 与小于它的邻点合并，用并查集维护连通块内所有邻点的最大标号。

查询时先查出 s 到 t 的 lim，只要当前点小于 lim 就倍增跳。注意跳出后再看是否要 +1，还有由题意得，答案初始化为 1。

::::success[Code]{open}

#include <bits/stdc++.h>
//#define int long long
#define PII pair < int , int >
#define x first
#define y second
using namespace std ; 
bool bbb ; 

namespace IO {
    constexpr auto maxn = 1 << 20;
    char in[maxn], out[maxn],*p1 = in,*p2 = in,*p3 = out;
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
#define flush() (fwrite(out,1,p3-out,stdout))
#define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
    class Flush {
    public:
        ~Flush() {
            flush();
        }
    } _;

    namespace usr {
        template<typename type>
        inline type read(type &x) {
            x = 0;
            bool flag(0);
            char ch = getchar();
            while (!isdigit(ch)) flag ^= ch == '-', ch = getchar();
            while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
            return flag ? x = -x : x;
        }
        template<typename type>
        inline void write(type x) {
            x < 0 ? x = -x, putchar('-') : 0;
            static short Stack[50], top(0);
            do Stack[++top] = x % 10, x /= 10;
            while (x);
            while (top) putchar(Stack[top--] | 48);
        }
        inline char read(char &x) {
            do x = getchar();
            while (isspace(x));
            return x;
        }
        inline char write(const char &x) {
            return putchar(x);
        }
        inline void read(char *x) {
            static char ch;
            read(ch);
            do *(x++) = ch;
            while (!isspace(ch = getchar()) && ~ch);
        }
        template<typename type>
        inline void write(type *x) {
            while (*x)putchar(*(x++));
        }
        inline void read(string &x) {
            static char ch;
            read(ch), x.clear();
            do x += ch;
            while (!isspace(ch = getchar()) && ~ch);
        }
        inline void write(const string &x) {
            for (int i = 0, len = x.length(); i < len; ++i)putchar(x[i]);
        }
        template<typename type, typename...T>
        inline void read(type &x, T&...y) {
            read(x), read(y...);
        }
        template<typename type, typename...T>
        inline void write(const type &x, const T&...y) {
            write(x), putchar(' '), write(y...), sizeof...(y) ^ 1 ? 0 : putchar('\n');
        }
        template<typename type>
        inline void put(const type &x, bool flag = 1) {
            write(x), flag ? putchar('\n') : putchar(' ');
        }
    }
#undef getchar
#undef flush
#undef putchar
} using namespace IO::usr;

const int N = 5e5 + 5 , Lg = 20 ; 
int Tid , n , m , Q ; 
vector < int > g[N] , g2[N] ; 
int f[N] , ma[N] ; // c 表示 1 代价到的最大点
int st[Lg][N] ; 
int find(int x){ return f[x] == x ? x : f[x] = find(f[x]) ; }
void merge(int x , int y){
    x = find(x) , y = find(y) ; 
    if(x == y) return ; 
    f[x] = y , ma[y] = max(ma[x] , ma[y]) ; 
}
struct node{ int x , y , z ; } b[N] ; 
bool cmp(node x , node y){ return x.z < y.z ; }
int dep[N] , lim[Lg][N] , up[Lg][N] ; 
void dfs(int u , int fa){
    dep[u] = dep[fa] + 1 ; 
    lim[0][u] = u , up[0][u] = fa ; 
    for(int j = 1 ; j <= __lg(n) ; j++)
        up[j][u] = up[j - 1][up[j - 1][u]] , 
        lim[j][u] = max(lim[j - 1][u] , lim[j - 1][up[j - 1][u]]) ; 
    for(int v : g2[u]) if(v != fa)
        dfs(v , u) ; 
}
int query(int x , int y){
    int res = 0 ; 
    if(dep[x] < dep[y]) swap(x , y) ; 
    for(int i = __lg(n) ; ~i ; i--)
        if(dep[up[i][x]] >= dep[y])
            res = max(res , lim[i][x]) , x = up[i][x] ; 
    if(x == y) return max(res , x) ; 
    for(int i = __lg(n) ; ~i ; i--)
        if(up[i][x] != up[i][y])
            res = max({res , lim[i][x] , lim[i][y]}) , 
            x = up[i][x] , y = up[i][y] ; 
    return max({res , x , y , up[0][x]}) ; 
}

bool eee ; 
signed main(){
    read(n , m , Q) ; 
    for(int i = 1 , u , v ; i <= m ; i++){
        read(u , v) ; 
        b[i] = {u , v , max(u , v)} ; 
        g[u].push_back(v) , 
        g[v].push_back(u) ; 
    }
    for(int i = 1 ; i <= n ; i++){
        f[i] = ma[i] = i ; 
        for(int v : g[i])
            ma[i] = max(ma[i] , v) ; 
    }
    for(int i = 1 ; i <= n ; i++){
        for(int v : g[i]) if(v < i)
            merge(i , v) ; 
        st[0][i] = ma[find(i)] ; 
    }
    for(int j = 1 ; j <= __lg(n) ; j++)
        for(int i = 1 ; i <= n ; i++)
            st[j][i] = st[j - 1][st[j - 1][i]] ; 
    for(int i = 1 ; i <= n ; i++) f[i] = i , ma[i] = i ; 
    sort(b + 1 , b + m + 1 , cmp) ; 
    for(int i = 1 ; i <= m ; i++){
        int x = find(b[i].x) , y = find(b[i].y) ; 
        if(x == y) continue ; 
        g2[b[i].x].push_back(b[i].y) , g2[b[i].y].push_back(b[i].x) ; 
        f[x] = y ; 
    }
    dfs(1 , 0) ; 
    while(Q--){
        int s , t , ans = 1 ; read(s , t) ; 
        int lm = query(s , t) ; 
        for(int j = __lg(n) ; ~j ; j--)
            if(st[j][s] < lm) s = st[j][s] , ans += (1 << j) ; 
        put(ans + (s < lm)) ; 
    }
    return 0 ; 
}

::::