BZOJ 2049 [SDOI2008] Cave 洞穴勘測：Link-Cut Tree 動態連通性

題目背景

n 個洞穴（節點），初始無邊。支援三種操作：

• Connect u v：添加邊 (u,v)
• Destroy u v：刪除邊 (u,v)
• Query u v：詢問 u、v 是否連通

保證任意時刻任意兩點間至多一條路徑（即圖始終為森林）。n ≤ 10,000，m ≤ 200,000。

核心數據結構：Link-Cut Tree (LCT)

LCT 維護動態森林，支援：

• link(u, v)：連接兩棵樹（u 為根）
• cut(u, v)：斷開邊 (u,v)
• findRoot(u)：查找 u 所在樹的根（判斷連通性）

均攤時間複雜度 O(log n)。

LCT 關鍵操作實現

Splay 輔助函數

bool isRoot(int x) {  // 判斷是否為 Splay 根（非虛樹根）
    return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}

void pushDown(int x) {  // 下推翻轉標記
    if (rev[x]) {
        rev[x] = 0;
        swap(ch[x][0], ch[x][1]);
        if (ch[x][0]) rev[ch[x][0]] ^= 1;
        if (ch[x][1]) rev[ch[x][1]] ^= 1;
    }
}

核心操作：Access、MakeRoot、Link、Cut

// 將 x 到根的路徑變為右側鏈，返回原根
void access(int x) {
    for (int y = 0; x; y = x, x = fa[x]) {
        splay(x);
        ch[x][1] = y;
    }
}

// 使 x 成為所在樹的根
void makeRoot(int x) {
    access(x);
    splay(x);
    rev[x] ^= 1;
}

// 連接 u、v（假設不同樹）
void link(int u, int v) {
    makeRoot(u);
    fa[u] = v;
}

// 斷開 u、v 間的邊
void cut(int u, int v) {
    makeRoot(u);
    access(v);
    splay(v);
    if (ch[v][0] == u && !ch[u][1]) {  // 確保直接相連
        ch[v][0] = fa[u] = 0;
    }
}

// 查找根節點
int findRoot(int x) {
    access(x);
    splay(x);
    while (pushDown(x), ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
}

完整解題流程

int main() {
    int n = read(), m = read();
    char op[10];
    while (m--) {
        scanf("%s", op);
        int u = read(), v = read();
        if (op[0] == 'C') link(u, v);
        else if (op[0] == 'D') cut(u, v);
        else puts(findRoot(u) == findRoot(v) ? "Yes" : "No");
    }
    return 0;
}

複雜度與優化

• 時間：O(m log n) — 每操作均攤 O(log n)
• 空間：O(n) — 樹節點數組
• I/O 優化：scanf/printf + 快速讀入函數

關鍵點總結

1. 題目保證「任意兩點間至多一條路徑」⇔ 動態森林，完美契合 LCT。
2. makeRoot 通過 access + splay + rev 實現根的切換，是 LCT 靈活性核心。
3. cut 前必須 makeRoot(u) 確保 u 為根，再 access(v) 將路徑暴露於 v 的 Splay 中。
4. 連通性判斷：findRoot(u) == findRoot(v)。

延伸閱讀

LCT 亦可維護路徑信息（如最大值、和），支援路徑查詢/修改。本題僅用其連通性功能，是 LCT 入門的經典題目。