如何理解 Tarjan 的 LCA 演算法？

12-29

如題，幾乎所有的資料都只是在講解怎麼做（演算法的步驟），卻沒有說明為什麼這樣做（演算法的正確性）。

我學會這個演算法是在高一， @riteme 教的。（最近公共祖先(LCA) - riteme.site）

他當時的解釋是這樣，記憶猶新：

一個熊孩子Link從一棵有根樹的最左邊最底下的結點灌岩漿，Link表示很討厭這種倒著長的樹。
岩漿會不斷的注入，直到注滿整個樹…
如果岩漿灌滿了一棵子樹，Link發現樹的另一邊有一棵更深的子樹，Link會先去將那棵子樹灌滿。

岩漿只有在迫不得已的情況下才會向上升高，找到一個新的子樹繼續注入。
機(yu)智(chun)的Link發現了找LCA的好方法，即如果兩個結點都被岩漿燒掉時，他們的LCA即為那棵子樹上岩漿最高的位置。

比較反對題目評論裡面直接叫人模擬一遍的做法。因為感性理解演算法是很重要的一環。

「能夠證明這個演算法的正確性」和「能夠自己想出來這個演算法」境界差距相當大。

與之類似地，我給高一的學弟學妹講Dijkstra的時候，往往用這樣一個說法：

假設你的邊是水槽，可以流過水，水的流速總是1。

那麼：你往S號點裡面注水，那麼凡是與S號點聯通的點，都會被水流到。

而點p第一次被水流到的時刻，就是S到p的最短路徑的值。這是顯然的。

如何模擬這個操作？

如果我們在t時刻到達了點x，那麼與x相連的節點都會被流到，如果邊權為w，那麼將會在w+t時刻流到。

我們給每個點標記一下dis：「最早將會在什麼時刻流到」，然後每次取出dis最小的點，這個dis值就是到它的最短路徑了；然後更新它能流到的點。特別地，在演算法最開始，把S點在0時刻流到。

複雜度 $O(n^2)$ ——這就是Dijkstra演算法。

如何優化？

根據上文所述，我們有一大堆事件——事件的形式是這樣：有一條水流將在t時刻流到x點。

搞一個「時間隊列」，每次取出t值最小的事件，顯然它最先發生。這樣我們就不用暴力查找哪個點最先被流到了。

用優先隊列（堆）或者平衡樹來實現時間隊列。複雜度降到 $O(E log V)$ ——這就是堆優化Dijkstra演算法。

這個說法是怎麼來的呢？也是在高一，我還不會最短路的時候，遇到了最短路的題目。我於是模擬水的流動，腦補出了一個演算法，交題，過了。

後來我才知道，我腦補出的那玩意叫做「堆優化Dijkstra」。

我的建議是：如果演算法可以感性理解，就要先嘗試著感性理解（但是自己要有能力證明）。

謝邀。

這個演算法我學不會。

你可以去看一下 hihoCoder 上的講解

領會精神不畫圖。忘了大概tarjan的LCA是哪個演算法……如果沒記錯八成是那個給樹標號的演算法。不管是不是我就bb這個演算法了。

這個演算法最值得學習的地方是對樹的轉化。本來運用RMQ求區間最小值和LCA是兩個不同的問題，但是設計者非常巧妙地一次DFS標號就把兩個問題結合在了一起。

假如我DFS過程中，我們先到了A點之後才到的B點，我們發現DFS過程中總會經過公共祖先。而且我們發現DFS過程中（只是A到B這一段）最接近root的一個節點也是他們的LCA。然後我們就可以按照距離根的距離把樹標號，A到B最小的數字就是對應的LCA。

為了便於處理，那麼我們到不妨直接給整棵樹從1到n標號。按照DFS的順序，如果已經標號的那麼我就pass。並記錄下經過了這個點，沒標號的就給一個最大的編號。

然後把整個遍歷的順序扔到數組裡。（說實話如果遞歸寫起來挺爽的）。

這時，我們如果需要求A到B的LCA就是求這個數組裡A到B的最小值就行了。

強行解釋一波。

嘗試對樹進行DFS，考慮每訪問到樹上的某一個節點（粉色），整棵樹都可以被分為三部分：已經訪問的部分（綠色）、當前訪問的鏈（黃色）、未訪問的部分（紅色）。

不妨只考慮處理當前節點與已訪問節點的查詢。對於已訪問和正在訪問的節點，可以將它們按照與當前節點的LCA分類（下圖中的A，B，C三部分）。

如果可以在dfs時維護這個劃分，那麼問題已經解決了。

當處理節點x時，對於所有詢問(x,y)（dfn(y)&

這個劃分可以用並查集維護，保證每次集合S的代表元素是x的祖先即可。

具體地，每次訪問x的子樹y後，把集合y合併到集合x上，這樣，在訪問x的其他子樹時，就能保證

y所在集合的代表元是x
訪問完成x的所有子樹後，x的所有子樹都被合併到集合x上

如果手動模擬一遍，可以注意到：

當前全體集合的所有代表元素恰好是從根到x的鏈上的所有節點
所有已訪問節點的集合都被合併到它的父節點的集合上

這個演算法手動模擬對理解還是相當有幫助的。

noip基本是不卡倍增的

因為聯賽緊就只講了tarjan的強聯通和割點

先佔坑，學完了之後再來答

tarjan三件套都是基於dfs的

用兩個數組來記錄時間戳和他能到達的最小時間戳

這是三個演算法的核心

真是大一，還不會。抱歉