（我?guī)啄隂]來過了）提示：只有算法，沒有基礎(chǔ)

樹，一種詭異?玄學(xué)?好用的數(shù)據(jù)結(jié)構(gòu)，因其特殊的結(jié)構(gòu)性質(zhì)從而具有廣泛的應(yīng)用性，其中二叉樹最為臭名昭著著名。上圖：

搞錯(cuò)了，再來一張

其中關(guān)于樹的一個(gè)重要算法就是求任意兩節(jié)點(diǎn)的最近公共祖先（LCA）。如上圖，8和6的最近公共祖先為1，4和9的LCA為2。通過求出LCA，我們可以得出兩點(diǎn)間距離以及等等。

例題：洛谷P3379（https://www.luogu.com.cn/problem/P3379）

讀題，我們需要求多組點(diǎn)的LCA。作為0基礎(chǔ)，我們先想最暴力的方法。

1、最暴力的方法就是分別讓兩個(gè)點(diǎn)向上找，直到兩個(gè)點(diǎn)相遇。

以8、6為例，路徑為

8->5->2->1

6->3->1

但這種方法基本只能騙分，1≤N,M≤500000不用想會(huì)妥妥的T飛~~~

于是我們需要一種優(yōu)化來減少我們的數(shù)據(jù)處理量，于是

2、倍增——一種利用二進(jìn)制優(yōu)化的算法——誕生了。

倍增倍增，以成倍增長來達(dá)到減少運(yùn)算次數(shù)，2的冪次方無疑是一個(gè)好用的東西。

眾所周知，任何一個(gè)數(shù)都能用不相同的2的冪次方之和來表達(dá)。那么我們就可以一次跳2的某次方步，來減少我們向上找的次數(shù)。用上面的圖可能不太能顯現(xiàn)出來，我們換一張圖：

上圖中，如果尋找17和18的LCA，按照第一種暴力：

17?>14?>10?>7?>3
18?>16?>12?>8?>5?>3

而如果用了倍增優(yōu)化：

17?>3
18?>5?>3

運(yùn)算量大大減少。

可以算出，此時(shí)算法的時(shí)間復(fù)雜度為O(nlogn)。

而想要實(shí)現(xiàn)這種想法，我們就需要進(jìn)行一些處理：

我們首先明確要使用到的變量：

首先需要知道，我們要把他們的各個(gè)i^2級(jí)祖先求出來。

我們運(yùn)用dfs，從根節(jié)點(diǎn)開始將整個(gè)樹遍歷一遍，在此過程中記錄每個(gè)節(jié)點(diǎn)的深度和他的父親。

求出每個(gè)節(jié)點(diǎn)的父親后，我們需要有一步非常重要的轉(zhuǎn)化，那就是通過遞推把它的各級(jí)祖先求出來。核心代碼：

預(yù)處理完成之后，我們就要著手于實(shí)現(xiàn)我們剛才所說的優(yōu)化了。

我們已經(jīng)求出來所有節(jié)點(diǎn)的深度和它2^i級(jí)的所有祖先，現(xiàn)在要找x和y的最近公共祖先，那么肯定會(huì)有fa[x][k]=fa[y][t]（因?yàn)橹辽儆懈鳛楣沧嫦龋?，而如果k≠t，x和y就不能同時(shí)進(jìn)行。所以我們需要把這兩個(gè)節(jié)點(diǎn)的深度先提升到同一高度，再統(tǒng)一向上找。

在將兩個(gè)節(jié)點(diǎn)提升到同一高度后，我們就可以進(jìn)行核心LCA了。

這里有一個(gè)點(diǎn)要注意，x和y的公共祖先可能不止一個(gè)，但最近公共祖先唯一確定。

我們很有可能會(huì)直接“跳過”x和y的LCA，跑到了另一個(gè)更高的公共祖先。

我們在跳的時(shí)候不能直接跳到它們的LCA，因?yàn)檫@可能會(huì)誤判，比如4和5，在跳的時(shí)候，我們可能會(huì)認(rèn)為2是它們的LCA，但2只是它們的祖先，它們的LCA其實(shí)是3。

所以我們需要跳到它們LCA的下面一層，然后輸出該層節(jié)點(diǎn)的父親，那么就是它們的LCA了，而且不會(huì)產(chǎn)生上文“跳過”的情況

這樣我們就實(shí)現(xiàn)了利用倍增尋找樹上兩點(diǎn)的LCA，常數(shù)優(yōu)化什么的就別管了（誒嘿）

全代碼如下：

另外還有一些別的例題，如洛谷P3884

尋找LCA還有一種方法叫做

3、樹鏈剖分（樹剖）

這個(gè)算法極其玄學(xué)（以至于我現(xiàn)在都不會(huì)），所以鴿到下期

完結(jié)撒花

祈愿胡桃加夜蘭加護(hù)摩

誒我上一篇文章怎么也這樣結(jié)尾