如何使用HLD查找LCA？

Question

我有一棵樹。我要回答的查詢，如：路徑

我使用重輕分解上的路徑

獲取和

1. 增值。樹中有n個節點和m查詢。對於HLD，當我知道最低公共祖先時，我可以將u和v的任何查詢分成兩個不同的查詢：從u到lca和v到。因此，查詢將在O(log^2n)時間（log從u和v到lca和log爲重路徑上的分段樹）上回答。

   如您所知，HLD內置於O(n)時間，因此總時間爲O(n + m*log^2n)。我的問題是如何使用已建立的HLD來查找LCA。我無法發明算法。

   我可以使用二進制爬行來獲得LCA，但需要預處理O(nlogn)，這會使漸近行爲變得更糟。我也可以使用範圍最小查詢，這不會浪費時間，但我想在此過程中使用HLD。感謝您的任何想法！

Answer 1

假設我們知道如何檢查一個節點是否是另一個節點的祖先（我們可以通過預先計算輸入時間以及在深度優先遍歷期間離開每個頂點的時間來完成）。這個想法是從其中一個頂點跳起來找到lca。

1. 讓我們看看當前路徑的最頂點。如果它不是另一個的祖先，我們跳到它然後去它的父親（在樹中更高的地方尋找lca）。

2. 否則，lca是在這條道路上的某個地方。我們可以對它進行二分搜索（它是最低的頂點，以至於它是另一個的祖先）。

我們最多訪問O(log n)路徑，我們通過二進制搜索其中之一。所以這種方法的總時間複雜度是每個查詢O(log n)。