程式面試：如何用 Link-Cut Tree 維護動態森林？

題干與適用場景

給定一個動態森林，邊會被加入或刪除，節點帶有整數值。需要支援 link(u,v)、cut(u,v)、路徑最大值查詢和路徑加值。請說明 Link-Cut Tree 的表示、access、makeroot、延遲標記、正確性與複雜度。

Sleator 與 Tarjan 的動態樹結構支援把兩棵樹連接和把一條邊切開，每個操作達到攤銷 O(log n)。面試重點是能否把「真實樹路徑」和「輔助 Splay 的首選路徑」區分開，而不是背出一段模板程式碼。

面試官考察點

• 是否知道 Link-Cut Tree 維護 represented forest，並用輔助 Splay 保存 preferred path。
• 能否正確實作 isRoot、push、pull、旋轉和 splay。
• 是否理解 access 如何把節點到根的路徑改成 preferred path。
• 能否用 makeroot 的反轉標記支援無根路徑，並避免延遲標記順序錯誤。
• 是否在 link、cut 前驗證連通性和邊確實存在。
• 能否說明攤銷 O(log n)，以及陣列、遞迴深度和隨機測試風險。

回答前需要釐清的問題

1. 結構保證始終是森林，還是可能出現環？Link-Cut Tree 不負責一般圖的連通性維護。
2. 路徑更新是加法、賦值還是同時需要最大/最小值？不同操作需要不同聚合與延遲標記。
3. 節點值還是邊值？若是邊值，可把邊映射為虛擬節點。
4. 操作是否需要持久化、並行，或只需單執行緒在線處理？
5. 輸入是否包含重複 link、不存在的 cut 和自環？

30 秒回答框架

我會用每個節點一個輔助 Splay，ch 表示 Splay 子樹，fa 表示輔助父節點或路徑父節點。access 從節點向上遍歷，逐步把右子樹替換為已處理路徑；makeroot 先 access 再翻轉整棵輔助樹。link 在確認不連通後 makeroot，再連接；cut makeroot(u)、access(v)，檢查 v 的左子樹是否正好是 u，再斷開。每次修改前 push，修改後 pull；操作攤銷 O(log n)。

分步驟深入解答

1. 表示兩種樹關係

輔助 Splay 的左右孩子描述 preferred path 上的順序；fa 在節點是輔助根時不代表 Splay 父子，而代表 represented tree 中的路徑父節點。因此 isRoot(x) 必須判斷 x 是否不是父節點的左右孩子，不能只檢查 fa[x] == 0。

2. 維護聚合和延遲標記

對路徑最大值，pull(x) 彙總自身值和兩個 Splay 子樹的最大值。路徑加值可用 add 標記；路徑反轉用 rev 標記交換左右孩子。push(x) 必須先把 rev 傳播，再傳播 add，或在實作中明確兩者可交換的代數關係。

pull(x): mx[x] = max(value[x], mx[ch[x][0]], mx[ch[x][1]])
applyAdd(x,d): value[x] += d; mx[x] += d; add[x] += d
applyRev(x): swap(ch[x][0], ch[x][1]); rev[x] ^= true

3. 實作 access

設 last = 0，從 x 向 fa[x] 走：先 splay(y)，把 y 的右孩子設為 last，pull(y)，再把 last 設為 y 並繼續。迴圈結束後 splay 原始 x。這樣 x 到 represented root 的路徑被拆成一條 preferred path，x 的 Splay 順序可用於路徑聚合。

4. 實作 makeroot

makeroot(x) 執行 access(x)，隨後給 x 打 rev 標記。此時 x 成為 represented tree 的根，後續 link(x,y) 才能把兩棵樹正確連接。不能直接遞迴翻轉整棵 represented tree；反轉只需要延遲到輔助 Splay。

5. 實作 link 與 cut

link(x,y) 先 makeroot(x)，確認 findroot(y) != x，再令 fa[x] = y。cut(x,y) 先 makeroot(x)、access(y)，此時若邊存在，y 的左孩子應為 x 且 x 沒有右孩子；斷開 ch[y][0] 並清除其父指標。檢查條件可避免切掉路徑上的其他節點。

6. 查詢和更新路徑

split(x,y) 等價於 makeroot(x); access(y)，此時 y 的輔助 Splay 包含 x 到 y 的路徑。讀取 mx[y] 得到最大值；路徑加值則對 y 應用 applyAdd。查詢前後不需要恢復 preferred path，因為下一次 access 會重新整理它。

7. 複雜度和測試

Sleator–Tarjan 分析給出 link、cut、root、evert 等操作的攤銷 O(log n)，空間為 O(n)。用小規模森林與樸素鄰接表交叉測試：隨機產生合法 link/cut，比較路徑最大值和加值結果；額外涵蓋單點、反覆 makeroot、連續 access、非法 cut、所有值相等和負數。

高品質示範回答

我會把 fa 同時作為輔助父或路徑父，靠 isRoot 區分，避免把 represented tree 當成一棵普通二元樹。每個 Splay 節點維護值、子樹最大值、反轉和加法標記。access 從目標向根整理 preferred path；makeroot 在 access 後打反轉標記；split(x,y) 讓 y 的 Splay 表示 x 到 y 的路徑。

link 先 makeroot 並拒絕已連通節點；cut 先 makeroot/access，再確認 y 的左子樹正好是 x 後斷邊。每次旋轉前按祖先順序 push，修改後 pull。理論上操作攤銷 O(log n)、空間 O(n)，我會用樸素森林隨機交叉測試路徑聚合、非法操作和延遲標記組合。

常見錯誤

• 用 fa[x] == 0 判斷輔助根 → 路徑父節點可能非零 → 用 isRoot 檢查左右孩子關係。
• 忘記在旋轉前 push 祖先 → rev 或 add 未傳播，聚合錯誤 → 先收集祖先棧並反向 push。
• cut 不檢查邊 → 會切斷路徑中錯誤節點 → makeroot/access 後驗證左子樹結構。
• link 不檢查連通性 → 形成環，結構不再是森林 → 先 findroot 判斷。
• 把 access 後的 Splay 當作整棵 represented tree → 只能保證當前 preferred path → 透過下一次 access 重新組織。
• 只測查詢不測更新 → 延遲標記問題被隱藏 → 與樸素森林做隨機路徑加值交叉測試。

追問及應對

如何維護路徑最小值或 XOR 值？

替換 pull 的么半群聚合即可；XOR 在反轉時不受順序影響，非交換聚合則必須確認路徑方向和反轉後的合併順序。

如何把邊權納入路徑查詢？

把每條邊拆成一個虛擬節點，虛擬節點值為邊權，再用普通節點路徑聚合；link/cut 時維護對應虛擬節點生命週期。

為什麼 access 的舊右子樹可以直接替換？

舊右子樹仍透過 fa 保留 represented path 的父關係，只是不再是當前 preferred path。輔助 Splay 的孩子關係和路徑父關係分離，替換不會遺失森林結構。

能否支援路徑賦值？

可以增加賦值標記，並定義它覆蓋舊 add、更新 value/mx，再按明確順序傳播 rev。關鍵是標記組合必須有可證明的優先級。

如何證明 findroot 正確？

對 x 執行 access 後不斷 push 並沿最左孩子走到 Splay 最左節點；該節點對應 represented tree 根，再 splay 它以穩定後續操作。

什麼時候不該使用 Link-Cut Tree？

若森林靜態，可用 DFS/Euler Tour 或重鏈剖分；若是一般動態圖連通性或需要並行、持久化，Link-Cut Tree 的維護邊界和實作風險可能不合適。