我有一個演算法的問題。
有一棵可以動態增減節點的多元樹，一開始是空的。
有兩個針對此多元樹的操作，如下所述：
操作A: 增加節點
給定一個多元樹的節點x，以及給定一個要新增的節點y，讓y成為x的小孩。
這項操作會是O(1)。
操作B: 刪除節點
給定樹上兩個相異的葉子x和y，令x與y的least common ancestor為z，
此操作會刪除x至z、刪除y至z路徑上的所有節點（會刪除到x與y，但不刪除z）。
然後x至z、y至z路徑上剩餘下來的子樹，統統接到z上。
問題是...請實作操作B，
讓這棵多元樹經過多次操作後，
總共的時間複雜度為O(n)，n為增加節點的次數。
先謝謝大家。 :)
-
PS: 這是我最近在研究Edmonds' blossom shrinking algorithm遇到的問題。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.73.157
※ 編輯: DJWS 來自: 220.137.73.157 (10/31 21:23)