BZOJ 2791 Poi2012 Rendezvous：倍增 LCA 處理內向森林

題目大意

給定一棵內向森林（每個節點出度 ≤ 1），多次查詢：給兩點 a, b，求非負整數對 (x, y) 使從 a 走 x 步、從 b 走 y 步到達同一點。優先條件：
1. 存在解。
2. max(x, y) 最小。
3. min(x, y) 最小。
4. x ≥ y（為了輸出唯一，非題目原意）。

結構分析

• 內向森林：每棵樹最終進入一個環，環上每節點出度 1 指向環上下一節點。
• 定義 root[x]：從 x 出發第一個到達的環上節點。
• 若 root[a] != root[b] 且不在同一環 → 無解。
• 若在同一棵樹（同一環）：最優會合點為 LCA。
• 若在同環但不同樹：會合點必為 root[a] 或 root[b]，分別計算步數取最優。

倍增 LCA

預處理 fa[u][k]（2^k 祖先）與 dpt[u]（到環距離）。環上節點深度為 0，fa[u][0] 指向環上下一節點。

核心代碼

#include <bits/stdc++.h>
using namespace std;
const int M = 500500;
int n, q, T;
int a[M], v[M], on_ring[M], pos[M], sz[M];
int fa[M][20], dpt[M], root[M];

void dfs(int x) {
    v[x] = T;
    if (v[a[x]] == T) { // 找到環
        int len = 1;
        for (int i = a[x]; i != x; i = a[i]) ++len;
        for (int i = x; ; i = a[i]) {
            on_ring[i] = T; pos[i] = len; root[i] = i; sz[T] = len;
            if (a[i] == x) break;
        }
        return;
    }
    if (!v[a[x]]) dfs(a[x]);
    if (!on_ring[x]) {
        fa[x][0] = a[x];
        dpt[x] = dpt[a[x]] + 1;
        root[x] = root[a[x]];
    }
}

int lca(int x, int y) {
    if (dpt[x] < dpt[y]) swap(x, y);
    for (int k = 19; k >= 0; --k)
        if (dpt[fa[x][k]] >= dpt[y]) x = fa[x][k];
    if (x == y) return x;
    for (int k = 19; k >= 0; --k)
        if (fa[x][k] != fa[y][k]) x = fa[x][k], y = fa[y][k];
    return fa[x][0];
}

int dist_on_ring(int x, int y, int p) { // 環上從 x 到 y 步數
    return (y - x + p) % p;
}

void solve(int x, int y) {
    if (on_ring[root[x]] != on_ring[root[y]]) { printf("-1 -1\n"); return; }
    if (root[x] == root[y]) {
        int z = lca(x, y);
        printf("%d %d\n", dpt[x] - dpt[z], dpt[y] - dpt[z]);
        return;
    }
    int rx = root[x], ry = root[y];
    int p = sz[on_ring[rx]];
    int x1 = dpt[x] + dist_on_ring(pos[rx], pos[ry], p), y1 = dpt[y];
    int x2 = dpt[x], y2 = dpt[y] + dist_on_ring(pos[ry], pos[rx], p);
    // 比較 (max, min, x>=y)
    if (max(x1,y1) != max(x2,y2)) { if (max(x1,y1) < max(x2,y2)) printf("%d %d\n", x1, y1); else printf("%d %d\n", x2, y2); }
    else if (min(x1,y1) != min(x2,y2)) { if (min(x1,y1) < min(x2,y2)) printf("%d %d\n", x1, y1); else printf("%d %d\n", x2, y2); }
    else printf("%d %d\n", max(x1,y1), min(x1,y1));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) if (!v[i]) ++T, dfs(i);
    for (int k = 1; k < 20; ++k)
        for (int i = 1; i <= n; ++i) fa[i][k] = fa[fa[i][k-1]][k-1];
    while (q--) { int x, y; scanf("%d%d", &x, &y); solve(x, y); }
    return 0;
}

複雜度

• 預處理：O(N log N)（倍增）。
• 查詢：O(log N)。
• 空間：O(N log N)。

關鍵技巧

• DFS 同時檢測環、賦予環上位置 pos、樹深度 dpt、根標記 root。
• 環上距離用模運算 (y - x + p) % p。
• 多解優先級按題目條件依次比較。