1. 從一次線上故障說起為什么LCA值得你花時間搞懂去年幫一個朋友排查他們內部工具的一個性能問題場景很典型一個組織架構樹大概三萬多節(jié)點每次要計算兩個員工在組織樹里的最近共同上級。他們最初的實現是暴力往上爬——把A的所有祖先塞進一個集合然后B從自己開始往上走遇到的第一個在集合里的節(jié)點就是答案。單次查詢看著不慢幾十毫秒但架不住前端一個頁面要批量算幾百對頁面直接卡到轉圈。這個問題的本質就是LCALowest Common Ancestor最近公共祖先。聽起來像是算法競賽里的東西但只要你處理過任何樹形結構——組織架構、文件目錄、DOM節(jié)點、分類體系、依賴關系圖——你遲早會撞上它。而且一旦數據量上去暴力解法就會原形畢露。這篇內容我打算把LCA這件事從頭到尾講透。不是那種背個倍增模板就完事的講法而是把為什么會有多種解法、每種解法到底在權衡什么、什么場景該選哪個、寫的時候哪里最容易翻車這些真正影響你落地的東西說清楚。適合已經會寫基礎樹遍歷、但一遇到樹上路徑查詢就發(fā)怵的開發(fā)者也適合想系統梳理一遍這塊知識的老手?？赐昴銘撃茏龅侥玫揭粋€問題先判斷它是不是LCA再根據數據規(guī)模和查詢次數直接選出合適的方案而不是無腦套模板。2. LCA到底在解決什么問題把共同祖先翻譯成人話2.1 用家族樹理解最近公共祖先先把這個概念用最樸素的方式說清楚。想象一棵家族樹根節(jié)點是最老的祖先往下每一層是下一代?，F在給你兩個人問他倆血緣關系最近的那個共同長輩是誰注意最近兩個字是關鍵。往上數所有共同的長輩都算公共祖先但我們要的是**深度最大離他倆最近**的那一個。比如你和你堂哥你們的爺爺是LCA但曾祖父也是共同祖先只不過曾祖父更遠不是最近的。形式化一點給定一棵有根樹對于節(jié)點u和vLCA(u, v)是同時滿足是u的祖先且是v的祖先的節(jié)點中深度最大的那個。這里祖先通常包含節(jié)點自己——也就是說如果u本身就是v的祖先那LCA就是u。這個約定很重要很多實現細節(jié)都跟它有關。2.2 為什么暴力爬樹會崩復雜度賬要算清楚最直覺的做法有兩種。第一種是剛才說的集合法把u到根的路徑全標記然后v往上走找第一個標記點。第二種是先把兩個節(jié)點提到同一深度然后一起往上走直到相遇。這兩種做法單次查詢的復雜度都是O(樹高)。問題就出在這個樹高上。如果樹比較平衡高度是log級別那還行但現實中的樹經常退化成一條鏈——比如一個層層審批的組織、一個深度嵌套的目錄、一條長依賴鏈。這時候樹高就是節(jié)點數n單次查詢O(n)查詢m次就是O(nm)。三萬個節(jié)點、幾百次查詢直接就是千萬級操作卡頓是必然的。所以LCA的核心矛盾就一句話能不能把單次查詢從O(樹高)壓到O(log n)甚至O(1)代價是預處理。后面講的所有算法本質上都是在這條權衡線上找不同的位置。2.3 哪些真實場景會用到LCA別以為這只是刷題用的。我梳理幾個實際會碰到的組織架構/權限系統判斷兩個員工的共同上級用于審批流、權限繼承、匯報關系展示。文件系統求兩個路徑的最近公共目錄做相對路徑計算、文件同步的差異定位。前端DOM操作找兩個節(jié)點的最近公共父節(jié)點用于事件委托、選區(qū)處理、虛擬DOM diff。版本控制/依賴分析在提交歷史或依賴樹里找共同基點判斷分支從哪分叉。生物信息學進化樹里找物種的共同祖先。網絡路由在某些樹形拓撲里找共同上游節(jié)點?？闯鰜砹税芍灰愕臄祿菢湫位蛘吣苻D成樹形LCA就是個繞不開的基礎操作。理解了它等于拿到了一把處理樹形查詢的萬能鑰匙。3. 倍增法最通用的LCA解法也是面試最愛問的3.1 倍增的核心思想用二進制跳躍代替一步步爬倍增法Binary Lifting是我最推薦的入門方案因為它通用、好寫、好調而且能順帶解決一堆衍生問題比如求路徑上第k個祖先、路徑長度等。它的核心思想特別巧妙與其一步一步往上爬不如一次跳2的冪次步。就像你要走1000米不會一米一米挪而是先走512米、再256米……用二進制拆分快速到達。具體做法是預處理一個跳表up[i][j]表示節(jié)點i往上跳2^j步后到達的祖先。這個表可以遞推出來up[i][0] parent[i] // 跳1步就是父節(jié)點 up[i][j] up[ up[i][j-1] ][j-1] // 跳2^j步 先跳2^(j-1)再跳2^(j-1)第二行的遞推是整個算法的靈魂。它把跳一大步拆成跳兩小步從而能用已經算好的小步結果推出大步結果。這就是典型的動態(tài)規(guī)劃思想也是倍增法名字的由來。3.2 預處理一遍DFS把跳表建起來預處理分兩步。第一步是DFS/BFS求出每個節(jié)點的深度depth[i]和直接父節(jié)點parent[i]。第二步就是按上面的遞推式填up表。關于j的上界取LOG ceil(log2(n)) 1就夠了。因為樹最高n層任何跳躍需求都能用不超過log2(n)位的二進制表示。多留一位是防止邊界越界。import sys sys.setrecursionlimit(300000) def preprocess(n, adj, root): LOG (n).bit_length() # 等價于 ceil(log2(n1)) depth [0] * (n 1) up [[0] * LOG for _ in range(n 1)] # 迭代式DFS避免遞歸爆棧 parent [0] * (n 1) order [] stack [root] visited [False] * (n 1) visited[root] True while stack: u stack.pop() order.append(u) for v in adj[u]: if not visited[v]: visited[v] True parent[v] u depth[v] depth[u] 1 stack.append(v) # 填跳表 for i in range(1, n 1): up[i][0] parent[i] for j in range(1, LOG): for i in range(1, n 1): up[i][j] up[ up[i][j-1] ][j-1] return depth, up, LOG這里有個實操細節(jié)值得說我強烈建議用迭代式DFS而不是遞歸。遞歸寫起來是簡潔但樹一深比如退化成鏈Python默認遞歸深度1000直接爆棧C雖然棧大一些但幾萬層也懸。迭代式雖然代碼長一點但穩(wěn)。這個坑我踩過不止一次線上環(huán)境可不會給你調遞歸深度的機會。3.3 查詢先對齊深度再一起往上跳查詢LCA(u, v)分兩個階段邏輯非常清晰階段一把深的那個提到和淺的一樣深。假設depth[u] depth[v]那就把u往上跳depth[u] - depth[v]步。這個差值用二進制拆解對應到跳表上就是如果差值的第j位是1就跳2^j步。階段二如果此時u v說明v本來就是u的祖先直接返回。否則兩個節(jié)點一起往上跳從大到小嘗試。關鍵技巧是只要跳完之后兩個節(jié)點還不相等就跳。這樣最后一定會停在LCA的正下方再往上一步就是答案。def lca(u, v, depth, up, LOG): if depth[u] depth[v]: u, v v, u # 階段一對齊深度 diff depth[u] - depth[v] for j in range(LOG): if diff (1 j): u up[u][j] if u v: return u # 階段二一起往上跳 for j in range(LOG - 1, -1, -1): if up[u][j] ! up[v][j]: u up[u][j] v up[v][j] return up[u][0]階段二那個從大到小的循環(huán)方向特別重要必須從高位往低位試。因為我們要盡可能跳得遠但又不能跳過LCA。從大往小試能保證最后停在最近的位置。如果從小到大試會跳得不夠遠邏輯就錯了。這個細節(jié)很多人第一次寫會搞反。3.4 倍增法的復雜度與適用邊界預處理時間O(n log n)空間O(n log n)單次查詢O(log n)。這個復雜度對于絕大多數場景都夠用了。它的優(yōu)勢是通用性極強不要求樹是靜態(tài)的雖然動態(tài)更新跳表比較麻煩能處理任意形態(tài)的樹還能順便支持求第k個祖先這類操作。缺點是空間是n log n如果n到了百萬級內存會有點吃緊。提示如果n特別大比如10^6以上而查詢次數不多其實暴力法反而更劃算。別迷信高級算法選型要看具體數據規(guī)模。4. Tarjan離線算法查詢多、樹不動時的效率之王4.1 離線思維把所有查詢攢起來一起算倍增法是在線的——來一個查詢答一個。但如果你的場景是一次性拿到所有查詢然后批量出結果那Tarjan離線算法往往更快。Tarjan的核心是DFS 并查集。它利用DFS的回溯特性在遍歷樹的過程中順便把所有查詢都解決了。單次查詢的均攤復雜度接近O(1)整體是O(n m·α(n))其中α是并查集的反阿克曼函數實際可以當成常數。這個思路的巧妙之處在于它把查詢這件事融進了遍歷里而不是遍歷完再單獨查。對于查詢量巨大的場景比如m和n同量級甚至更大這個優(yōu)勢非常明顯。4.2 并查集在這里扮演什么角色理解Tarjan的關鍵是搞懂并查集維護的是什么。在DFS過程中每個節(jié)點有三種狀態(tài)未訪問、正在訪問在遞歸棧里、已訪問完子樹處理完畢。并查集維護的是已訪問完的節(jié)點的集合并且每個集合的代表元指向它當前能追溯到的、還在遞歸棧里的那個祖先。當DFS訪問到節(jié)點u處理所有跟u相關的查詢(u, v)時如果v還沒訪問跳過等以后v被訪問時再處理這對查詢。如果v已經訪問完了那么v所在并查集集合的代表元就是LCA(u, v)。為什么因為v已經處理完說明v的整棵子樹都遍歷過了而u還在棧里說明u是v的某個祖先方向上的節(jié)點。此時v能追溯到的、還在棧里的最深祖先恰好就是它和u的分叉點也就是LCA。4.3 完整實現與關鍵細節(jié)def tarjan_lca(n, adj, root, queries): # queries[u] [(v, query_id), ...] parent list(range(n 1)) # 并查集 ancestor [0] * (n 1) # 集合代表元對應的祖先 visited [False] * (n 1) answer [0] * len(queries) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] # 路徑壓縮 x parent[x] return x def dfs(u): visited[u] True ancestor[find(u)] u for v in adj[u]: if not visited[v]: dfs(v) parent[find(v)] find(u) # 合并子樹到u ancestor[find(u)] u # 處理與u相關的查詢 for (v, qid) in queries[u]: if visited[v]: answer[qid] ancestor[find(v)] dfs(root) return answer幾個容易翻車的點第一ancestor的更新時機。每次合并完子樹后要把合并后集合的ancestor重新指向u。因為合并后代表元可能變了不更新就會拿到錯誤的祖先。第二查詢要存雙向。因為處理(u,v)時可能v還沒訪問得等v被訪問時從v那邊再處理一次。所以queries[u]和queries[v]都要存這條查詢。第三遞歸深度問題。跟倍增法一樣深樹會爆棧。生產環(huán)境建議改迭代或者手動加大?？臻g。4.4 什么時候該選Tarjan而不是倍增判斷標準很簡單維度倍增法Tarjan離線查詢模式在線來一個答一個離線必須預先知道所有查詢單次查詢O(log n)均攤O(α(n))≈O(1)預處理O(n log n)無獨立預處理空間O(n log n)O(n m)實現難度中等中等偏上并查集易錯適用場景查詢少、需在線查詢海量、可離線如果你的查詢次數m遠大于nTarjan的均攤優(yōu)勢會非常明顯。但如果查詢是流式的、必須即時回答那只能選倍增。選型的第一原則永遠是先搞清楚你的查詢模式。5. 歐拉序 RMQ把LCA變成區(qū)間最值問題5.1 一個漂亮的轉化LCA等價于區(qū)間最小值這是我覺得LCA里最優(yōu)雅的一個思路。它把樹上問題轉化成了數組上的區(qū)間查詢問題。做法是對樹做一次DFS記錄歐拉序也叫DFS序的擴展版——每次進入一個節(jié)點記一次每次從子樹返回父節(jié)點時也記一次。這樣得到的序列長度是2n-1。同時記錄每個節(jié)點在序列中第一次出現的位置first[u]。關鍵結論LCA(u, v)就是歐拉序中first[u]到first[v]這段區(qū)間里深度最小的那個節(jié)點。為什么因為從u走到v在歐拉序上必然經過它們的LCA而且LCA是這段路徑上深度最小的點。這個性質把LCA問題完美地轉化成了**RMQ區(qū)間最小值查詢**問題。5.2 稀疏表ST表實現O(1)查詢既然變成了RMQ那就可以用經典的ST表Sparse Table來做到O(1)查詢。ST表的預處理是O(n log n)查詢O(1)。import math def build_euler(n, adj, root): euler [] # 歐拉序存節(jié)點 depth_arr [] # 對應深度 first [0] * (n 1) visited [False] * (n 1) def dfs(u, d): visited[u] True first[u] len(euler) euler.append(u) depth_arr.append(d) for v in adj[u]: if not visited[v]: dfs(v, d 1) euler.append(u) depth_arr.append(d) dfs(root, 0) return euler, depth_arr, first def build_st(depth_arr): m len(depth_arr) LOG m.bit_length() # st[i][j] 存區(qū)間 [i, i2^j-1] 中深度最小的節(jié)點在depth_arr中的下標 st [[0] * LOG for _ in range(m)] for i in range(m): st[i][0] i for j in range(1, LOG): for i in range(m - (1 j) 1): left st[i][j-1] right st[i (1 (j-1))][j-1] st[i][j] left if depth_arr[left] depth_arr[right] else right return st def query_lca(u, v, first, depth_arr, st, euler): l, r first[u], first[v] if l r: l, r r, l length r - l 1 k length.bit_length() - 1 left st[l][k] right st[r - (1 k) 1][k] idx left if depth_arr[left] depth_arr[right] else right return euler[idx]5.3 歐拉序方案的取舍這個方案的優(yōu)勢是查詢O(1)比倍增的O(log n)還快。而且思路清晰一旦理解了歐拉序的性質代碼其實不難寫。但它有幾個明顯的代價空間更大歐拉序長度是2n-1ST表又是(2n) log(2n)比倍增的n log n大一倍左右。預處理常數大建ST表的雙重循環(huán)實際跑起來比倍增的預處理慢。只適合靜態(tài)樹樹一變整個歐拉序和ST表都要重建。所以我的經驗是如果查詢量極大且樹完全靜態(tài)歐拉序ST表是最優(yōu)解否則倍增法更省心。別為了那點查詢速度提升把代碼復雜度拉高一大截維護成本也是成本。注意歐拉序的DFS同樣有遞歸深度問題。而且歐拉序長度是2n如果n很大光是存這個序列就要不少內存選型前先估一下。6. 四種解法橫向對比一張表幫你做選型決策前面講了四種主流方案這里做個系統對比方便你直接查表決策。方案預處理單次查詢空間在線/離線最適合的場景暴力爬樹O(1)O(樹高)O(n)在線樹淺、查詢極少倍增法O(n log n)O(log n)O(n log n)在線通用首選查詢中等Tarjan離線無均攤O(α(n))O(nm)離線查詢海量、可離線歐拉序STO(n log n)O(1)O(n log n)在線查詢極多、樹靜態(tài)選型的決策鏈路我一般是這么走的第一步看查詢模式。流式在線查詢排除Tarjan能批量離線Tarjan值得考慮。第二步看數據規(guī)模。n小幾千以內且查詢少暴力法最省事別過度設計。n大且查詢多上倍增或歐拉序。第三步看樹是否靜態(tài)。樹會動態(tài)變化倍增法改起來相對可控雖然也麻煩歐拉序基本要重建。第四步看查詢次數。查詢次數遠超n歐拉序的O(1)優(yōu)勢才體現得出來否則倍增的O(log n)完全夠用。我見過太多人一上來就寫歐拉序ST表結果數據規(guī)模才幾千純屬殺雞用牛刀代碼還容易寫錯。選型要匹配問題規(guī)模這是工程思維和刷題思維最大的區(qū)別。7. 實戰(zhàn)中那些文檔不會告訴你的坑7.1 根節(jié)點的父節(jié)點處理這是最經典的坑。根節(jié)點沒有父節(jié)點那up[root][0]填什么填0假設節(jié)點編號從1開始還是填自己填0的話如果查詢時不小心跳到了0后續(xù)up[0][j]全是0可能掩蓋邏輯錯誤。填自己的話跳過頭會原地打轉。我的建議是填0并且在查詢邏輯里保證永遠不會真正用到0這個越界值——因為對齊深度和一起跳的過程理論上不會讓節(jié)點跳到根之上。但為了保險可以在填表時把up[0][j]都設成0讓越界訪問有個確定的兜底。7.2 深度對齊時的循環(huán)方向階段一對齊深度時for j in range(LOG)從小到大還是從大到小其實都可以因為我們是按二進制位判斷的每一位獨立。但階段二一起跳的時候必須從大到小。這兩個循環(huán)方向不一樣很多人寫著寫著就混了。記住口訣對齊深度看位一起跳看大小。7.3 多組測試數據的初始化如果是在競賽或批量處理場景多組測試數據之間一定要徹底重置所有數組。我見過因為up表沒清干凈上一組數據殘留導致答案錯誤的案例。Python里重新分配數組最省心C里記得memset或者重新構造。7.4 節(jié)點編號從0還是從1開始這個看似小事實則影響巨大。從1開始的話0可以當哨兵從0開始的話就沒有天然的哨兵值了。我個人的習慣是統一從1開始編號把0留作哨兵能省掉很多邊界判斷。如果輸入是從0開始的讀入時統一加1。7.5 遞歸改迭代的通用套路前面反復提到遞歸爆棧。改迭代的通用做法是手動維護一個棧棧里存(節(jié)點, 父節(jié)點, 狀態(tài))狀態(tài)標記是第一次訪問還是回溯?；蛘吒唵蜗扔肂FS求出遍歷順序和父節(jié)點再按逆序處理回溯邏輯。對于倍增法其實只需要父節(jié)點和深度BFS一遍就夠了根本不需要DFS。這個優(yōu)化能同時解決爆棧和效率問題。8. 從LCA延伸出去幾個高頻衍生問題搞懂了LCA很多樹上查詢問題都能順手解決。這里列幾個最常見的延伸算是給你指個方向。樹上兩點距離。有了LCA距離公式就是depth[u] depth[v] - 2 * depth[lca(u,v)]。這個公式極其常用路徑長度、樹上最遠點對之類的問題都靠它。樹上路徑第k個節(jié)點。從u到v的路徑上第k個點先判斷k是否超過u到LCA的距離分兩種情況用倍增跳。這是倍增法跳表能力的直接應用。判斷一個點是否在兩點路徑上。點w在u-v路徑上當且僅當lca(u,w)w且lca(w,v)ww是u的祖先且是v的祖先方向或者更準確地用距離公式驗證。這類判斷在路徑覆蓋、樹上差分里很常見。樹上差分。給u到v的路徑上所有點加一個值可以用差分diff[u] 1, diff[v] 1, diff[lca] - 1, diff[parent(lca)] - 1最后子樹求和。這個技巧配合LCA能解決一大批路徑統計問題。這些延伸的共同點是LCA是它們的地基。地基打牢了上面的樓怎么蓋都行。所以別急著刷各種花哨的樹上問題先把LCA這幾種解法吃透后面會輕松很多。我個人在實際項目里的體會是真正高頻用到的其實就是倍增法這一種因為它通用、在線、好維護。Tarjan和歐拉序更像是特定場景的優(yōu)化手段知道原理、需要時能撿起來就行不必強求每種都背得滾瓜爛熟。把一種方案寫到閉著眼睛都不出錯比每種都半懂不懂要值錢得多。 LCA最近公共祖先算法詳解：倍增法、Tarjan離線與歐拉序RMQ選型指南
1. 從一次線上故障說起為什么LCA值得你花時間搞懂去年幫一個朋友排查他們內部工具的一個性能問題場景很典型一個組織架構樹大概三萬多節(jié)點每次要計算兩個員工在組織樹里的最近共同上級。他們最初的實現是暴力往上爬——把A的所有祖先塞進一個集合然后B從自己開始往上走遇到的第一個在集合里的節(jié)點就是答案。單次查詢看著不慢幾十毫秒但架不住前端一個頁面要批量算幾百對頁面直接卡到轉圈。這個問題的本質就是LCALowest Common Ancestor最近公共祖先。聽起來像是算法競賽里的東西但只要你處理過任何樹形結構——組織架構、文件目錄、DOM節(jié)點、分類體系、依賴關系圖——你遲早會撞上它。而且一旦數據量上去暴力解法就會原形畢露。這篇內容我打算把LCA這件事從頭到尾講透。不是那種背個倍增模板就完事的講法而是把為什么會有多種解法、每種解法到底在權衡什么、什么場景該選哪個、寫的時候哪里最容易翻車這些真正影響你落地的東西說清楚。適合已經會寫基礎樹遍歷、但一遇到樹上路徑查詢就發(fā)怵的開發(fā)者也適合想系統梳理一遍這塊知識的老手?？赐昴銘撃茏龅侥玫揭粋€問題先判斷它是不是LCA再根據數據規(guī)模和查詢次數直接選出合適的方案而不是無腦套模板。2. LCA到底在解決什么問題把共同祖先翻譯成人話2.1 用家族樹理解最近公共祖先先把這個概念用最樸素的方式說清楚。想象一棵家族樹根節(jié)點是最老的祖先往下每一層是下一代?，F在給你兩個人問他倆血緣關系最近的那個共同長輩是誰注意最近兩個字是關鍵。往上數所有共同的長輩都算公共祖先但我們要的是**深度最大離他倆最近**的那一個。比如你和你堂哥你們的爺爺是LCA但曾祖父也是共同祖先只不過曾祖父更遠不是最近的。形式化一點給定一棵有根樹對于節(jié)點u和vLCA(u, v)是同時滿足是u的祖先且是v的祖先的節(jié)點中深度最大的那個。這里祖先通常包含節(jié)點自己——也就是說如果u本身就是v的祖先那LCA就是u。這個約定很重要很多實現細節(jié)都跟它有關。2.2 為什么暴力爬樹會崩復雜度賬要算清楚最直覺的做法有兩種。第一種是剛才說的集合法把u到根的路徑全標記然后v往上走找第一個標記點。第二種是先把兩個節(jié)點提到同一深度然后一起往上走直到相遇。這兩種做法單次查詢的復雜度都是O(樹高)。問題就出在這個樹高上。如果樹比較平衡高度是log級別那還行但現實中的樹經常退化成一條鏈——比如一個層層審批的組織、一個深度嵌套的目錄、一條長依賴鏈。這時候樹高就是節(jié)點數n單次查詢O(n)查詢m次就是O(nm)。三萬個節(jié)點、幾百次查詢直接就是千萬級操作卡頓是必然的。所以LCA的核心矛盾就一句話能不能把單次查詢從O(樹高)壓到O(log n)甚至O(1)代價是預處理。后面講的所有算法本質上都是在這條權衡線上找不同的位置。2.3 哪些真實場景會用到LCA別以為這只是刷題用的。我梳理幾個實際會碰到的組織架構/權限系統判斷兩個員工的共同上級用于審批流、權限繼承、匯報關系展示。文件系統求兩個路徑的最近公共目錄做相對路徑計算、文件同步的差異定位。前端DOM操作找兩個節(jié)點的最近公共父節(jié)點用于事件委托、選區(qū)處理、虛擬DOM diff。版本控制/依賴分析在提交歷史或依賴樹里找共同基點判斷分支從哪分叉。生物信息學進化樹里找物種的共同祖先。網絡路由在某些樹形拓撲里找共同上游節(jié)點?？闯鰜砹税芍灰愕臄祿菢湫位蛘吣苻D成樹形LCA就是個繞不開的基礎操作。理解了它等于拿到了一把處理樹形查詢的萬能鑰匙。3. 倍增法最通用的LCA解法也是面試最愛問的3.1 倍增的核心思想用二進制跳躍代替一步步爬倍增法Binary Lifting是我最推薦的入門方案因為它通用、好寫、好調而且能順帶解決一堆衍生問題比如求路徑上第k個祖先、路徑長度等。它的核心思想特別巧妙與其一步一步往上爬不如一次跳2的冪次步。就像你要走1000米不會一米一米挪而是先走512米、再256米……用二進制拆分快速到達。具體做法是預處理一個跳表up[i][j]表示節(jié)點i往上跳2^j步后到達的祖先。這個表可以遞推出來up[i][0] parent[i] // 跳1步就是父節(jié)點 up[i][j] up[ up[i][j-1] ][j-1] // 跳2^j步 先跳2^(j-1)再跳2^(j-1)第二行的遞推是整個算法的靈魂。它把跳一大步拆成跳兩小步從而能用已經算好的小步結果推出大步結果。這就是典型的動態(tài)規(guī)劃思想也是倍增法名字的由來。3.2 預處理一遍DFS把跳表建起來預處理分兩步。第一步是DFS/BFS求出每個節(jié)點的深度depth[i]和直接父節(jié)點parent[i]。第二步就是按上面的遞推式填up表。關于j的上界取LOG ceil(log2(n)) 1就夠了。因為樹最高n層任何跳躍需求都能用不超過log2(n)位的二進制表示。多留一位是防止邊界越界。import sys sys.setrecursionlimit(300000) def preprocess(n, adj, root): LOG (n).bit_length() # 等價于 ceil(log2(n1)) depth [0] * (n 1) up [[0] * LOG for _ in range(n 1)] # 迭代式DFS避免遞歸爆棧 parent [0] * (n 1) order [] stack [root] visited [False] * (n 1) visited[root] True while stack: u stack.pop() order.append(u) for v in adj[u]: if not visited[v]: visited[v] True parent[v] u depth[v] depth[u] 1 stack.append(v) # 填跳表 for i in range(1, n 1): up[i][0] parent[i] for j in range(1, LOG): for i in range(1, n 1): up[i][j] up[ up[i][j-1] ][j-1] return depth, up, LOG這里有個實操細節(jié)值得說我強烈建議用迭代式DFS而不是遞歸。遞歸寫起來是簡潔但樹一深比如退化成鏈Python默認遞歸深度1000直接爆棧C雖然棧大一些但幾萬層也懸。迭代式雖然代碼長一點但穩(wěn)。這個坑我踩過不止一次線上環(huán)境可不會給你調遞歸深度的機會。3.3 查詢先對齊深度再一起往上跳查詢LCA(u, v)分兩個階段邏輯非常清晰階段一把深的那個提到和淺的一樣深。假設depth[u] depth[v]那就把u往上跳depth[u] - depth[v]步。這個差值用二進制拆解對應到跳表上就是如果差值的第j位是1就跳2^j步。階段二如果此時u v說明v本來就是u的祖先直接返回。否則兩個節(jié)點一起往上跳從大到小嘗試。關鍵技巧是只要跳完之后兩個節(jié)點還不相等就跳。這樣最后一定會停在LCA的正下方再往上一步就是答案。def lca(u, v, depth, up, LOG): if depth[u] depth[v]: u, v v, u # 階段一對齊深度 diff depth[u] - depth[v] for j in range(LOG): if diff (1 j): u up[u][j] if u v: return u # 階段二一起往上跳 for j in range(LOG - 1, -1, -1): if up[u][j] ! up[v][j]: u up[u][j] v up[v][j] return up[u][0]階段二那個從大到小的循環(huán)方向特別重要必須從高位往低位試。因為我們要盡可能跳得遠但又不能跳過LCA。從大往小試能保證最后停在最近的位置。如果從小到大試會跳得不夠遠邏輯就錯了。這個細節(jié)很多人第一次寫會搞反。3.4 倍增法的復雜度與適用邊界預處理時間O(n log n)空間O(n log n)單次查詢O(log n)。這個復雜度對于絕大多數場景都夠用了。它的優(yōu)勢是通用性極強不要求樹是靜態(tài)的雖然動態(tài)更新跳表比較麻煩能處理任意形態(tài)的樹還能順便支持求第k個祖先這類操作。缺點是空間是n log n如果n到了百萬級內存會有點吃緊。提示如果n特別大比如10^6以上而查詢次數不多其實暴力法反而更劃算。別迷信高級算法選型要看具體數據規(guī)模。4. Tarjan離線算法查詢多、樹不動時的效率之王4.1 離線思維把所有查詢攢起來一起算倍增法是在線的——來一個查詢答一個。但如果你的場景是一次性拿到所有查詢然后批量出結果那Tarjan離線算法往往更快。Tarjan的核心是DFS 并查集。它利用DFS的回溯特性在遍歷樹的過程中順便把所有查詢都解決了。單次查詢的均攤復雜度接近O(1)整體是O(n m·α(n))其中α是并查集的反阿克曼函數實際可以當成常數。這個思路的巧妙之處在于它把查詢這件事融進了遍歷里而不是遍歷完再單獨查。對于查詢量巨大的場景比如m和n同量級甚至更大這個優(yōu)勢非常明顯。4.2 并查集在這里扮演什么角色理解Tarjan的關鍵是搞懂并查集維護的是什么。在DFS過程中每個節(jié)點有三種狀態(tài)未訪問、正在訪問在遞歸棧里、已訪問完子樹處理完畢。并查集維護的是已訪問完的節(jié)點的集合并且每個集合的代表元指向它當前能追溯到的、還在遞歸棧里的那個祖先。當DFS訪問到節(jié)點u處理所有跟u相關的查詢(u, v)時如果v還沒訪問跳過等以后v被訪問時再處理這對查詢。如果v已經訪問完了那么v所在并查集集合的代表元就是LCA(u, v)。為什么因為v已經處理完說明v的整棵子樹都遍歷過了而u還在棧里說明u是v的某個祖先方向上的節(jié)點。此時v能追溯到的、還在棧里的最深祖先恰好就是它和u的分叉點也就是LCA。4.3 完整實現與關鍵細節(jié)def tarjan_lca(n, adj, root, queries): # queries[u] [(v, query_id), ...] parent list(range(n 1)) # 并查集 ancestor [0] * (n 1) # 集合代表元對應的祖先 visited [False] * (n 1) answer [0] * len(queries) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] # 路徑壓縮 x parent[x] return x def dfs(u): visited[u] True ancestor[find(u)] u for v in adj[u]: if not visited[v]: dfs(v) parent[find(v)] find(u) # 合并子樹到u ancestor[find(u)] u # 處理與u相關的查詢 for (v, qid) in queries[u]: if visited[v]: answer[qid] ancestor[find(v)] dfs(root) return answer幾個容易翻車的點第一ancestor的更新時機。每次合并完子樹后要把合并后集合的ancestor重新指向u。因為合并后代表元可能變了不更新就會拿到錯誤的祖先。第二查詢要存雙向。因為處理(u,v)時可能v還沒訪問得等v被訪問時從v那邊再處理一次。所以queries[u]和queries[v]都要存這條查詢。第三遞歸深度問題。跟倍增法一樣深樹會爆棧。生產環(huán)境建議改迭代或者手動加大?？臻g。4.4 什么時候該選Tarjan而不是倍增判斷標準很簡單維度倍增法Tarjan離線查詢模式在線來一個答一個離線必須預先知道所有查詢單次查詢O(log n)均攤O(α(n))≈O(1)預處理O(n log n)無獨立預處理空間O(n log n)O(n m)實現難度中等中等偏上并查集易錯適用場景查詢少、需在線查詢海量、可離線如果你的查詢次數m遠大于nTarjan的均攤優(yōu)勢會非常明顯。但如果查詢是流式的、必須即時回答那只能選倍增。選型的第一原則永遠是先搞清楚你的查詢模式。5. 歐拉序 RMQ把LCA變成區(qū)間最值問題5.1 一個漂亮的轉化LCA等價于區(qū)間最小值這是我覺得LCA里最優(yōu)雅的一個思路。它把樹上問題轉化成了數組上的區(qū)間查詢問題。做法是對樹做一次DFS記錄歐拉序也叫DFS序的擴展版——每次進入一個節(jié)點記一次每次從子樹返回父節(jié)點時也記一次。這樣得到的序列長度是2n-1。同時記錄每個節(jié)點在序列中第一次出現的位置first[u]。關鍵結論LCA(u, v)就是歐拉序中first[u]到first[v]這段區(qū)間里深度最小的那個節(jié)點。為什么因為從u走到v在歐拉序上必然經過它們的LCA而且LCA是這段路徑上深度最小的點。這個性質把LCA問題完美地轉化成了**RMQ區(qū)間最小值查詢**問題。5.2 稀疏表ST表實現O(1)查詢既然變成了RMQ那就可以用經典的ST表Sparse Table來做到O(1)查詢。ST表的預處理是O(n log n)查詢O(1)。import math def build_euler(n, adj, root): euler [] # 歐拉序存節(jié)點 depth_arr [] # 對應深度 first [0] * (n 1) visited [False] * (n 1) def dfs(u, d): visited[u] True first[u] len(euler) euler.append(u) depth_arr.append(d) for v in adj[u]: if not visited[v]: dfs(v, d 1) euler.append(u) depth_arr.append(d) dfs(root, 0) return euler, depth_arr, first def build_st(depth_arr): m len(depth_arr) LOG m.bit_length() # st[i][j] 存區(qū)間 [i, i2^j-1] 中深度最小的節(jié)點在depth_arr中的下標 st [[0] * LOG for _ in range(m)] for i in range(m): st[i][0] i for j in range(1, LOG): for i in range(m - (1 j) 1): left st[i][j-1] right st[i (1 (j-1))][j-1] st[i][j] left if depth_arr[left] depth_arr[right] else right return st def query_lca(u, v, first, depth_arr, st, euler): l, r first[u], first[v] if l r: l, r r, l length r - l 1 k length.bit_length() - 1 left st[l][k] right st[r - (1 k) 1][k] idx left if depth_arr[left] depth_arr[right] else right return euler[idx]5.3 歐拉序方案的取舍這個方案的優(yōu)勢是查詢O(1)比倍增的O(log n)還快。而且思路清晰一旦理解了歐拉序的性質代碼其實不難寫。但它有幾個明顯的代價空間更大歐拉序長度是2n-1ST表又是(2n) log(2n)比倍增的n log n大一倍左右。預處理常數大建ST表的雙重循環(huán)實際跑起來比倍增的預處理慢。只適合靜態(tài)樹樹一變整個歐拉序和ST表都要重建。所以我的經驗是如果查詢量極大且樹完全靜態(tài)歐拉序ST表是最優(yōu)解否則倍增法更省心。別為了那點查詢速度提升把代碼復雜度拉高一大截維護成本也是成本。注意歐拉序的DFS同樣有遞歸深度問題。而且歐拉序長度是2n如果n很大光是存這個序列就要不少內存選型前先估一下。6. 四種解法橫向對比一張表幫你做選型決策前面講了四種主流方案這里做個系統對比方便你直接查表決策。方案預處理單次查詢空間在線/離線最適合的場景暴力爬樹O(1)O(樹高)O(n)在線樹淺、查詢極少倍增法O(n log n)O(log n)O(n log n)在線通用首選查詢中等Tarjan離線無均攤O(α(n))O(nm)離線查詢海量、可離線歐拉序STO(n log n)O(1)O(n log n)在線查詢極多、樹靜態(tài)選型的決策鏈路我一般是這么走的第一步看查詢模式。流式在線查詢排除Tarjan能批量離線Tarjan值得考慮。第二步看數據規(guī)模。n小幾千以內且查詢少暴力法最省事別過度設計。n大且查詢多上倍增或歐拉序。第三步看樹是否靜態(tài)。樹會動態(tài)變化倍增法改起來相對可控雖然也麻煩歐拉序基本要重建。第四步看查詢次數。查詢次數遠超n歐拉序的O(1)優(yōu)勢才體現得出來否則倍增的O(log n)完全夠用。我見過太多人一上來就寫歐拉序ST表結果數據規(guī)模才幾千純屬殺雞用牛刀代碼還容易寫錯。選型要匹配問題規(guī)模這是工程思維和刷題思維最大的區(qū)別。7. 實戰(zhàn)中那些文檔不會告訴你的坑7.1 根節(jié)點的父節(jié)點處理這是最經典的坑。根節(jié)點沒有父節(jié)點那up[root][0]填什么填0假設節(jié)點編號從1開始還是填自己填0的話如果查詢時不小心跳到了0后續(xù)up[0][j]全是0可能掩蓋邏輯錯誤。填自己的話跳過頭會原地打轉。我的建議是填0并且在查詢邏輯里保證永遠不會真正用到0這個越界值——因為對齊深度和一起跳的過程理論上不會讓節(jié)點跳到根之上。但為了保險可以在填表時把up[0][j]都設成0讓越界訪問有個確定的兜底。7.2 深度對齊時的循環(huán)方向階段一對齊深度時for j in range(LOG)從小到大還是從大到小其實都可以因為我們是按二進制位判斷的每一位獨立。但階段二一起跳的時候必須從大到小。這兩個循環(huán)方向不一樣很多人寫著寫著就混了。記住口訣對齊深度看位一起跳看大小。7.3 多組測試數據的初始化如果是在競賽或批量處理場景多組測試數據之間一定要徹底重置所有數組。我見過因為up表沒清干凈上一組數據殘留導致答案錯誤的案例。Python里重新分配數組最省心C里記得memset或者重新構造。7.4 節(jié)點編號從0還是從1開始這個看似小事實則影響巨大。從1開始的話0可以當哨兵從0開始的話就沒有天然的哨兵值了。我個人的習慣是統一從1開始編號把0留作哨兵能省掉很多邊界判斷。如果輸入是從0開始的讀入時統一加1。7.5 遞歸改迭代的通用套路前面反復提到遞歸爆棧。改迭代的通用做法是手動維護一個棧棧里存(節(jié)點, 父節(jié)點, 狀態(tài))狀態(tài)標記是第一次訪問還是回溯?；蛘吒唵蜗扔肂FS求出遍歷順序和父節(jié)點再按逆序處理回溯邏輯。對于倍增法其實只需要父節(jié)點和深度BFS一遍就夠了根本不需要DFS。這個優(yōu)化能同時解決爆棧和效率問題。8. 從LCA延伸出去幾個高頻衍生問題搞懂了LCA很多樹上查詢問題都能順手解決。這里列幾個最常見的延伸算是給你指個方向。樹上兩點距離。有了LCA距離公式就是depth[u] depth[v] - 2 * depth[lca(u,v)]。這個公式極其常用路徑長度、樹上最遠點對之類的問題都靠它。樹上路徑第k個節(jié)點。從u到v的路徑上第k個點先判斷k是否超過u到LCA的距離分兩種情況用倍增跳。這是倍增法跳表能力的直接應用。判斷一個點是否在兩點路徑上。點w在u-v路徑上當且僅當lca(u,w)w且lca(w,v)ww是u的祖先且是v的祖先方向或者更準確地用距離公式驗證。這類判斷在路徑覆蓋、樹上差分里很常見。樹上差分。給u到v的路徑上所有點加一個值可以用差分diff[u] 1, diff[v] 1, diff[lca] - 1, diff[parent(lca)] - 1最后子樹求和。這個技巧配合LCA能解決一大批路徑統計問題。這些延伸的共同點是LCA是它們的地基。地基打牢了上面的樓怎么蓋都行。所以別急著刷各種花哨的樹上問題先把LCA這幾種解法吃透后面會輕松很多。我個人在實際項目里的體會是真正高頻用到的其實就是倍增法這一種因為它通用、在線、好維護。Tarjan和歐拉序更像是特定場景的優(yōu)化手段知道原理、需要時能撿起來就行不必強求每種都背得滾瓜爛熟。把一種方案寫到閉著眼睛都不出錯比每種都半懂不懂要值錢得多。