LCA思想：在求解最近公共祖先為問題上，用到的是Tarjan的思想，從根結(jié)點開始形成一棵深搜樹，非常好的處理技巧就是在回溯到結(jié)點u的時候，u的子樹已經(jīng)遍歷，這時候才把u結(jié)點放入合并集合中， 這樣u結(jié)點和所有u的子樹中的結(jié)點的最近公共祖先就是u了，u和還未遍歷的所有u的兄弟結(jié)點及子樹中的最近公共祖先就是u的父親結(jié)點。以此類推。。這樣我們在對樹深度遍歷的時候就很自然的將樹中的結(jié)點分成若干的集合，兩個集合中的所屬不同集合的任意一對頂點的公共祖先都是相同的，也就是說這兩個集合的最近公共最先只有一個。對于每個集合而言可以用并查集來優(yōu)化，時間復(fù)雜度就大大降低了，為O(n + q)，n為總結(jié)點數(shù)，q為詢問結(jié)點對數(shù)。

轉(zhuǎn)載于:https://www.cnblogs.com/hujunzheng/p/3945885.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的LCA算法的理解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。