沿父指標走一步很便宜,但每次查詢都走數千步,就會重複同樣工作。若預先存下每個頂點走 1、2、4、8 等二的冪次步之後會到哪裏,長距離向上行走便可由其二進位數字組合而成。
這是二進位提升,即祖先倍增。倍增原理類似二進位快速冪,但組合的是父映射,而非數值。我們先證明每個表項的含義,再用它找最近共同祖先。後者需要自己的不變量:懂得快速跳躍,並不等於已知道哪些跳躍安全。
預處理後,樹與所選根保持固定。此方法提供靜態祖先及距離查詢;若要維護路徑上持續改變的一般數值,不能因此省略重鏈分解等方法各自的設計。
分清根樹深度與表格約定
輸入是一棵非空無向樹,頂點為 ,選定根為 。樹連通且無環,因此任意兩頂點之間有唯一簡單路徑。深度 是根到 路徑上的邊數。非根頂點的父頂點,是該路徑上緊接在它之前的頂點。
定義 13.2.1
(真實祖先與固定在根的父映射)
對整數 , 的第 祖先是向根方向恰好走 次父步驟所到的頂點。它存在,當且僅當 。第零祖先就是 本身;超過根便沒有真實祖先。
只為建立表格,定義處處有值的映射 :非根處使用真實父頂點,根處設 。儲存
這裏的指數計算重複函數合成次數。表格跳躍若走得太遠,映射就停在根。這種補值令全部查表合法,但不改變真實第 祖先的存在規則。
定義 13.2.2
(最近共同祖先)
頂點的真實祖先,恰為其根路徑上的全部頂點,包含自己。兩個頂點的根路徑交集,是共同起始路徑;其中最深頂點便是唯一最近共同祖先,簡稱 LCA。「最近」在此指深度最大,不是頂點標籤最小。
組合同一父操作的冪
定理 13.2.3
(以二進位合成求第 k 個祖先)
對每個頂點 與每個整數 ,把 寫成 ,其中 。從 出發,對每個滿足 的 ,把當前頂點換成它在第 行的值 ,結果就是 的第 個祖先;而且每個這樣的 都是已儲存的行,行數 是 的二進位位數,至少為 。
證明
(倍增與二進位數字)
基底行套用 一次。若第 行套用 次,連用該行兩次便套用 次,以歸納證明下一行。
把合法要求寫成 ,其中 。每遇一個設定位元,就把目前頂點換成第 行所給的祖先。因為它們都是同一映射的冪,組合恰好套用 共 次。已選步數的每個部分和都不超過 ,所以過程不需使用根以上的人工補值。
頂點樹的深度至多 。因此使用 行,編號 0 至 ,已能表示全部合法距離。單頂點情況仍保留一行基底。讀取位元及表格之前,先核查要求的深度上限。
證明透視
為甚麼表中填充的部分從不被碰到
證明只需要 提供的一件事:所選各個二的冪的每個部分和都不超過 ,所以每個中間頂點都是真實祖先,填充規則 從未被使用。跳躍的次序無關緊要,因為同一個映射的各次冪互相可交換。行數則是另一個純算術的事實: 限制了 的最高設定位。
反例模式
根的補值不代表有無限多個祖先
深度為 2 的頂點,第 3 祖先不存在。若根指向自己的表格沒有先核查深度,卻仍會傳回根。這描述補值後的映射,不是三次真實父步驟。
程式在 時傳回 None,並拒絕負 。特別地,根的第零祖先是根,第 1 祖先卻不存在。極大的非法 亦須先被深度上限排除,不能讓它請求不存在的表格行。
一棵分枝樹的跳躍表
例題 13.2.4
(用一步與四步組合五步向上行走)
取八個頂點,根為 0,邊為 、、、、、、,兩支在頂點 2 分開。因 有三個二進位數字,三行表格已足夠。
| 頂點 | 深度 | :一步 | :兩步 | :四步 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 2 | 2 | 1 | 0 | 0 |
| 3 | 3 | 2 | 1 | 0 |
| 4 | 4 | 3 | 2 | 0 |
| 5 | 5 | 4 | 3 | 1 |
| 6 | 3 | 2 | 1 | 0 |
| 7 | 4 | 6 | 2 | 0 |
從 5 走五步,使用 :先到 ,再到 。亦可先走四步到 1,再一步到 0,兩個次序都合成同樣五個父步驟。第 6 祖先要求傳回 None,即使補值後合成會停在 0。
例題 13.2.5
(路徑圖與全深度祖先)
設樹為以 為根的路徑 ,故 , 行分別存放 步的跳躍。 的第七個祖先用 :,接著 ,再 ,正是 。全深度的祖先 :,然後 ,即根。請求 時回傳 None,雖然填充後的合成也會落在 。
先等深,再比較兩條向上路徑
求 時,先把較深端點向上提升深度差。LCA 不變,因為略過的頂點都比另一端點深,不可能是共同祖先。目前兩頂點深度已相同。若它們重合,該頂點就是答案,包含一個原端點是另一個祖先的情況。
否則,兩個目前頂點不同,並都嚴格位於真正 LCA 下方。考慮各走同樣 步:若提議的祖先不同,兩次跳躍仍嚴格在 下方,可以安全採用;若祖先相同,則跳躍已到達或越過 ,採用它可能跳過答案。
定理 13.2.6
(LCA 掃描的正確性)
把 中較深的一個向上提升深度差。若兩個頂點相同,該頂點就是 。否則依 掃描,每當兩者在第 行的祖先不同,就把兩個頂點都換成它們。掃描結束時得到兩個不同的頂點,其共同父頂點就是 。
證明
(由大至小的不等跳躍)
等深且不同的兩頂點,到 LCA 的正距離相同,記為 。向上路徑在到達 前不相交,其後重合。因此 成立,當且僅當 。固定在根的表格補值,使超過根的跳躍也維持兩端相等。
提議祖先不同時,把兩端都換成它們,令 減少 ,LCA 不變;否則兩端不動。由第 行掃至第 0 行。起初 。若處理第 行之前有 ,則或者 而不跳,或者減去 後留下 。
歸納可知處理第 0 行後有 。目前兩頂點是 的不同子頂點,所以共同父頂點恰為答案。執行過程不必事先知道 ;兩個查表值不等,已是每次安全移動的證明。
證明透視
為甚麼用不相等作判斷
掃描只用到未知 LCA 的一個事實:兩個位於 下方同樣距離 的頂點,它們在第 行的祖先不同,當且僅當 。所以「不同」保證這次跳躍仍嚴格停在 之下,而「相同」只表示跳躍會到達或越過 ,並不說明 有多遠。不變量 使掃描成為對 的二分搜尋:每一層要麼因 而保持 不變,要麼減去 並使 。若從第 層向上掃描就會失敗,因為較早取的小跳躍可能留下一個需要更大跳躍的距離,而更大的跳躍已經過去了。
反例模式
提議祖先相等時跳躍,可能跳過所求祖先
取邊 、、,根為 0。2 與 3 的 LCA 是 1,但兩步祖先都為 0。若只因兩項相等,就把兩端都移到 0,便會越過 1 而丟掉答案。
正確迴圈只在提議祖先不同時移動,保持在 LCA 下方。提議相等,應嘗試較短跳躍。等深後的相等檢查卻不同:若目前頂點本身重合,就已到答案,應立即傳回。
常見錯誤
(由小到大掃描層次)
層次必須由 掃到 。取兩個位於其 LCA 下方距離 的頂點。若由小到大掃描,第 層的祖先不同,兩者上移一步,剩下 ;第 層的提議已經相同,所以不動;掃描結束時仍在 LCA 下方兩條邊,回傳的是真正 LCA 的一個子頂點,答案錯誤。由大到小則先試 步跳躍,拒絕它,再取 步跳躍,拒絕 步跳躍,停在距離 處,其父頂點就是 LCA。
推導無權邊距離
定理 13.2.7
(由深度與 LCA 得出距離)
對樹中的頂點 ,設其最近共同祖先為 ,則唯一的 – 路徑的邊數為
證明
(先向上再向下)
路徑沿 條邊從 向上到 ,再沿 條邊向下到 。兩段沒有共同的邊,因為在 之下它們位於不同的根路徑上;若 或 ,其中一段為空。把兩個數目相加就得到公式。
常見錯誤
(深度不是加權距離)
公式計算邊數。若邊有其他長度或權重,普通深度不是加權距離,不能不改儲存量與證明就直接代用。
例題 13.2.8
(先等深,再停在分枝點下方)
八頂點樹中,5 深度為 5,7 深度為 4。先把 5 提升一步至 4,便比較深度同為 4 的頂點 4、7。四步提議都為 0,兩步提議都為 2,兩組都不採用。
一步提議是不同的 3、6,於是移到這兩點,再傳回共同父頂點 2。因此 ,距離為 。真實路徑為 ,恰有五條邊。
對端點 3、5,等深時已把 5 帶到 3,所以同步跳躍迴圈前便傳回 LCA。兩端相同時,LCA 是該頂點,距離為零。
具有樹契約的可執行實作
建構子接受正整數 、整數端點配對的無向邊串列,以及整數根標籤。它核查端點、恰好 個邊實例及連通性。後兩個條件已保證是樹,即使輸入嘗試包含自環或重複邊也一樣:連通圖已需要 條生成樹邊,不會剩額外邊實例給自環、平行副本或環。
廣度優先遍歷不使用遞歸,記錄父頂點及深度,並在頂點首次進入佇列時標記。查詢標籤必須在 ;非法及負標籤會在任何查表前被拒絕。建構子只讀邊串列,不會修改它。
from collections import deque
class AncestorTable:
def __init__(self, n, edges, root=0):
if n <= 0 or not 0 <= root < n:
raise ValueError("a nonempty tree and a valid root are required")
graph = [[] for _ in range(n)]
edge_count = 0
for u, v in edges:
if not (0 <= u < n and 0 <= v < n):
raise ValueError("edge endpoint outside the vertex range")
graph[u].append(v)
graph[v].append(u)
edge_count += 1
if edge_count != n - 1:
raise ValueError("a tree must have exactly n - 1 edges")
parent = [-1] * n
depth = [0] * n
parent[root] = root
pending = deque([root])
reached = 1
while pending:
vertex = pending.popleft()
for neighbor in graph[vertex]:
if parent[neighbor] == -1:
parent[neighbor] = vertex
depth[neighbor] = depth[vertex] + 1
reached += 1
pending.append(neighbor)
if reached != n:
raise ValueError("the tree must be connected")
self.n = n
self.depth = depth
self.up = [parent]
levels = max(1, (n - 1).bit_length())
for _ in range(1, levels):
previous = self.up[-1]
self.up.append([previous[previous[v]] for v in range(n)])
def _vertex(self, vertex):
if not 0 <= vertex < self.n:
raise IndexError("vertex outside the tree")
def ancestor(self, vertex, k):
self._vertex(vertex)
if k < 0:
raise ValueError("the ancestor distance must be nonnegative")
if k > self.depth[vertex]:
return None
level = 0
while k:
if k & 1:
vertex = self.up[level][vertex]
k >>= 1
level += 1
return vertex
def lca(self, u, v):
self._vertex(u)
self._vertex(v)
if self.depth[u] < self.depth[v]:
u, v = v, u
u = self.ancestor(u, self.depth[u] - self.depth[v])
if u == v:
return u
for level in range(len(self.up) - 1, -1, -1):
if self.up[level][u] != self.up[level][v]:
u = self.up[level][u]
v = self.up[level][v]
return self.up[0][u]
def distance(self, u, v):
common = self.lca(u, v)
return self.depth[u] + self.depth[v] - 2 * self.depth[common]
程式假設標籤、數目及 符合整數承諾。合法等深提升不會傳回 None,因為所走距離不超過較深端點的深度。單頂點表格為 [[0]],祖先距離零傳回 0,任何正距離傳回 None,而 lca(0,0) 傳回 0。
命題 13.2.9
(祖先表的開銷)
對有 個頂點的樹,預處理需時 、佔用相同量級的空間;在索引、位元運算與整數算術都是常數時間的假設下,每次祖先、LCA 或距離查詢需時 。
證明
(計算行數與迴圈次數)
對合法輸入,建立圖及根樹父項需 時間。表格有 個單元,填表需 時間,所以預處理和儲存為 ;每次祖先、LCA 或距離查詢,在普通索引、位元操作及整數算術假設下,最壞需 時間。小小的 包含單頂點情況。這不是任意長整數的位元複雜度界。
改選根會改變祖先關係,也可能改變 LCA,但不改變唯一無向路徑及其邊數。建構後若改動樹邊,預處理便失效;動態拓撲需要另一個數據結構或重新建立。
練習與完整解答
快速檢查
(1. 八頂點例子中,求 5 的第 3、第 5、第 6 祖先。最後要求為何不能只看補值後查表結果?)
解答 · 1. 分清真實步驟與根補值
第 3 祖先是路徑 上的 2,第 5 祖先是 0。由於 5 的深度為 5,第 6 祖先不存在,函數傳回 None。補值映射合成六次雖會停在 0,卻不是第六個真實祖先。深度檢查維持查詢原本含義。
快速檢查
(2. 用兩步表項推導四步表項 。沒有行儲存三步,為何同一表格仍能回答三步要求?)
解答 · 2. 組合已存冪次得到其他距離
、,所以 。三步使用 :先一步到 4,再兩步到 2。各行儲存二的冪,而二進位組合提供這些冪次的每個合法和。
快速檢查
(3. 求例子中的 LCA(5,7) 及邊距離。等深後,真正採用了哪次同步跳躍?)
解答 · 3. 最後走父邊前,維持在共同祖先下方
先把 5 提升至 4,四步及兩步提議都相同,所以不採用。一步提議為 3、6,兩端移到那裏後,其父頂點 2 就是 LCA。邊距離為 ,與路徑 相符。
快速檢查
(4. 樹有 0-1,並在 1 接葉 2、3。為何不能從 2、3 採用相等的兩步提議?甚麼相等情況才應立即傳回答案?)
解答 · 4. 提議跳躍相等,不等於目前頂點相等
兩步提議都到 0,越過真正 LCA 1,採用它們會失去最近共同祖先。所以同步迴圈只採用不同提議。等深後,若目前兩端本身相等,該共同頂點已是 LCA,才立即傳回。兩個相等檢查的含義與用途不同。
快速檢查
(5. 在路徑 0-1-2 上,比較根為 0 及根為 2 時的 LCA(0,2)。邊距離有否改變?)
解答 · 5. 祖先依賴根,距離則不依賴
根為 0 時 LCA 是 0,根為 2 時 LCA 是 2,兩者各自代表相應根路徑的共同起始部分。唯一無向路徑仍有兩條邊,兩種根下的深度公式都得 2。若要使用新根的祖先關係,須重新預處理。
快速檢查
(6. 輸入 n=4,邊為 (0,1),(1,2),(2,0),已有 n−1 條邊,為何建構子仍須拒絕?無向邊串列為何同時有正確邊數及連通性就足夠?)
解答 · 6. 只有邊數不能證明是樹
三條邊在三個頂點形成三角形,頂點 3 卻孤立,所以連通性檢查失敗。每個連通無向圖都有含 個邊實例的生成樹。若整個輸入亦只有同樣數目,全部邊就必須是生成樹邊,沒有額外邊可形成環、自環或平行副本。兩個條件都是接受樹契約所需。