P3533 [POI2012] RAN-Rendezvous 题解

Laoshan_PLUS · 2024-05-30 20:42:31 · 题解

基环树典型题。

题意

给定一个 n 个顶点的内向基环森林和 q 组询问，每个询问包含两个点 a,b，求点对 (x,y) 满足：

从 a 出发走 x 步和从 b 出发走 y 步会到达同一个点。
在 1 的基础上如果有多解，那么要求 \max(x,y) 最小。
在 1 和 2 的基础上如果有多解，那么要求 \min(x,y) 最小。
如果在 1、2、3 的基础上仍有多解，那么要求 x\ge y。

如果不存在满足条件 1 的 (x,y)，输出 -1 -1。

解析

仍然用基环树的惯用套路，分类讨论。

若存在满足条件 1 的 \boldsymbol{(x,y)}，即从 \boldsymbol a 出发走 \boldsymbol x 步和从 \boldsymbol b 出发走 \boldsymbol y 步会到达同一个点，那么定义这个点为 \boldsymbol{a,b} 两点的 “交汇点”。

若 a,b 都不在一个基环树里，直接输出 -1 -1。
若 a,b 在基环树环上同一点的子树内，则此时的交汇点就是 a,b 的 LCA，不难证明。
否则，答案要么是 a 所在子树根节点，要么是 b 所在子树根节点，同样不难证明：因为环是单向的，所以只要不是在这两个根节点，都会徒增路程而没有任何效益。

那么有了思路，接下来考虑如何实现。

首先肯定是一个 DFS 判基环树，对每个点作标记，然后就可以特判掉情况 1。

其次，对于情况 2，我们需要求出两点 LCA。肯定是用倍增，所以我们需要预处理 \textit{fa} 和 \textit{dep} 数组，所以需要求出每棵子树根节点。根节点一定在环上，所以 DFS 判环，再对于环上每个点预处理一下即可。然后对于情况 2 就可以直接求出 LCA。

最后，对于情况 3，我们需要求出：\textit{dep}(i)，表示子树上的点 i 到子树根节点的距离，这里我们在预处理 LCA 时已经求过；\textit{dis}(i,j)，表示环上 i,j 两点间距离，这里我们用前缀和的思想，对每个环跑一遍即可求出。统计答案的时候按照题目所给的意思比较两种答案最后输出即可。

实现

#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 5e5 + 5;
int n, q;
vector<int> g[MAXN], G[MAXN];
int tr[MAXN];
bool vis[MAXN];
int stk[MAXN], top;
bool ring[MAXN], ins[MAXN];
int len[MAXN], dis[MAXN], ist[MAXN], tot;
int dep[MAXN], fa[MAXN][21];

void isring(int u) {
    if (ins[u]) {
        ring[u] = 1;
        for (int i = top; stk[i] != u; i--) ring[stk[i]] = 1;
        return;
    }
    if (vis[u]) return;
    vis[u] = 1;
    stk[++top] = u;
    ins[u] = 1;
    for (auto v : g[u]) isring(v);
    --top;
    ins[u] = 0;
}

void getfa(int u, int fno, int uu) {
    // cout << u << '\n';
    tr[u] = uu;
    fa[u][0] = fno;
    dep[u] = dep[fno] + 1;
    for (int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto v : G[u]) if (!ring[v]) getfa(v, u, uu);
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20; i >= 0; i--)
        if (dep[fa[u][i]] >= dep[v])
            u = fa[u][i];
    if (u == v) return v;
    for (int i = 20; i >= 0; i--)
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    return fa[u][0];
}

void ringlen(int u, int t, int fno) {
    if (dis[u]) return;
    ist[u] = t;
    len[t]++;
    dis[u] = dis[fno] + 1;
    for (auto v : g[u]) if (ring[v]) ringlen(v, t, u);
}

bool check(int a1, int a2, int b1, int b2) {
    if (max(a1, a2) != max(b1, b2)) return max(a1, a2) < max(b1, b2);
    if (min(a1, a2) != min(b1, b2)) return min(a1, a2) < min(b1, b2);
    return a1 >= a2;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    // freopen("ran3c.in", "r", stdin);
    // freopen("ans.out", "w", stdout);
    cin >> n >> q;
    for (int i = 1, v; i <= n; i++) {
        cin >> v;
        // if (i == v) continue;
        g[i].push_back(v);
        G[v].push_back(i);
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << i << ": ";
    //     for (auto v : G[i]) cout << v << ' ';
    //     cout << '\n';
    // }
    for (int i = 1; i <= n; i++) if (!vis[i]) isring(i);
    // for (int i = 1; i <= n; i++) cout << ring[i] << '\n';
    for (int i = 1; i <= n; i++) if (ring[i]) getfa(i, 0, i);
    for (int i = 1; i <= n; i++) if (ring[i] && !dis[i]) ringlen(i, ++tot, 0);
    // cout << find(1) << ' ' << find(4) << ' ' << find(5) << '\n';
    // cout << len[ist[1]] << '\n';
    int x, y;
    while (q--) {
        cin >> x >> y;
        if (ist[tr[x]] != ist[tr[y]]) cout << "-1 -1\n";
        else if (tr[x] == tr[y]) {
            int LCA = lca(x, y);
            cout << dep[x] - dep[LCA] << ' ' << dep[y] - dep[LCA] << '\n';
        } else {
            int ans1 = dep[y] - 1 + (dis[tr[x]] - dis[tr[y]] + len[ist[tr[x]]]) % len[ist[tr[x]]];
            int ans2 = dep[x] - 1 + (dis[tr[y]] - dis[tr[x]] + len[ist[tr[x]]]) % len[ist[tr[x]]];
            // cout << dep[x] - 1 << ' ' << ans1 << ' ' << ans2 << ' ' << dep[y] - 1 << ' ';
            // cout << check(dep[x] - 1, ans1, ans2, dep[y] - 1) << '\n';
            if (check(dep[x] - 1, ans1, ans2, dep[y] - 1)) cout << dep[x] - 1 << ' ' << ans1 << '\n';
            else cout << ans2 << ' ' << dep[y] - 1 << '\n';
        }
    }

    return 0;
}