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

· · 题解

不会 Kruscal 重构树建议先去这里学习。

在博客食用更佳。

思路分析

这是一个一般图，所以两点间枚举路径显然是不可能的。

但是注意到求的是前缀最大值的最小数量，这个东西看起来就有比较强的性质，所以从这里入手。

这里先定义 S_i 为点 i 能够只花费 1 的代价到达的点集，显然 S_i 是一个连通块。

设S_i' 为 S 的导出子图集合。

对于 v\in S_i' 现在无论 i 怎么走都一定需要花费 1 的代价去走到 S 之外的点。

这里就可以贪心选择最大的点 mx_i\in S_i' 这样就可以让花费 2 的代价能够到达的连通块更大（这里显然，合法性由可以反复经过一个点提供）。

那就把问题转换求最少跳几次 mx_s 能够使 mx_s > a_{s,t}，其中 a_{s,t} 表示从 s 到 t 的最小瓶颈路。

那做法就很显然了，最小瓶颈路直接用 Kruscal 重构树求出，u 到 v 边权设为 \max(u,v)。

然后根据 mx_i 建立倍增数组，查询的时候直接跳倍增即可。

时间复杂度 O(N\log N)。

Code

#include<bits/stdc++.h>
#define int long long
#define PII pair<int, int>

using namespace std;

int id, n, m, Q;
vector<int> g[500010], G[1000010];
int ltc;
PII cx[500010];
int fa[500010], mx[500010][21];
PII edge[500010];
int F[1000010], pw2[21], lgn[1000010], ds;
int st[1000010][21];
int dfn[1000010], dfc;
int val[1000010];

int compare(int x, int y)
{
    return dfn[x] < dfn[y] ? x : y;
}

int find(int u)
{
    return fa[u] == u ? u : fa[u] = find(fa[u]);
}

void init_dfn(int u, int f)
{
    dfn[u] = ++dfc;
    st[dfn[u]][0] = f;
    for(int v : G[u]) init_dfn(v, u);
}

void init_ST()
{
    pw2[0] = 1;
    for(int t = 1;t <= 20;t ++) pw2[t] = pw2[t - 1] * 2;
    for(int i = 1;i <= ds;i ++) lgn[i] = lgn[i >> 1] + (i > 1);
    for(int t = 1;t <= 20;t ++)
    {
        for(int i = 1;i + pw2[t] - 1 <= ds;i ++)
        {
            st[i][t] = compare(st[i][t - 1], st[i + pw2[t - 1]][t - 1]);
        }
    }
    for(int t = 1;t <= 20;t ++) mx[n][t] = n;
    for(int t = 1;t <= 20;t ++)
    {
        for(int i = 1;i <= n;i ++) mx[i][t] = mx[mx[i][t - 1]][t - 1];
    }
}

int get_LCA(int u, int v)
{
    if(u == v) return u;
    int l = dfn[u], r = dfn[v];
    if(l > r) swap(l, r);
    ++ l;
    int t = lgn[r - l + 1];
    return compare(st[l][t], st[r - pw2[t] + 1][t]);
}

int query(int u, int v)
{
    if(u >= v) return 1;
    if(mx[u][0] >= v) return 2;
    int cnt = 0;
    for(int t = 20;t >= 0;t --)
    {
        if(mx[u][t] < v)
        {
            u = mx[u][t];
            cnt += pw2[t];
        }
    }
    return cnt + 2;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> Q;
    ds = n;
    for(int i = 1;i <= n;i ++)
    {
        mx[i][0] = i;
        fa[i] = i;
    }
    for(int i = 1;i <= m;i ++)
    {
        int u, v;
        cin >> u >> v;
        if(u < v) swap(u, v);
        edge[i] = {u, v};
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i < n; i++)
    {
        for(int v : g[i])
        {
            int fv = find(v);
            mx[i][0] = max(mx[i][0], mx[fv][0]);
            if(fv < i) fa[fv] = i;
        }
    }
    for(int i = 1;i <= n;i ++) fa[i] = i;
    sort(edge + 1, edge + m + 1);
    for(int i = 1;i <= m;i ++)
    {
        int u = edge[i].first, v = edge[i].second;
        int fu = find(u), fv = find(v);
        if(fu == fv) continue;
        ++ ds;
        G[ds].push_back(fu);
        G[ds].push_back(fv);
        fa[fu] = ds;
        fa[fv] = ds;
        fa[ds] = ds;
        F[fu] = ds;
        F[fv] = ds;
        val[ds] = u;
    }
    init_dfn(ds, 0);
    init_ST();
    for(int i = 1;i <= Q;i ++)
    {
        int s, t;
        cin >> s >> t;
        int LCA = get_LCA(s, t);
        cout << query(s, val[LCA]) << "\n";
    }
    return 0;
}