前置必看

上回書說到，彼時的LCA，海中有一個玄學的做法，名為樹剖，全名樹鏈剖分。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 首先聲明定義:

1. 重兒子：父親節(jié)點的所有兒子中子樹結點數(shù)目最多（size最大）的結點；

2. 輕兒子：父親節(jié)點中除了重兒子以外的兒子；

3. 重邊：父親結點和重兒子連成的邊；

4. 輕邊：父親節(jié)點和輕兒子連成的邊；

5. 重鏈：由多條重邊連接而成的路徑；

6. 輕鏈：由多條輕邊連接而成的路徑；

樹剖的核心思想，就是把一棵樹分為數(shù)條不相交的輕重鏈。

我們定義，對于一個節(jié)點x來說，size[x]代表x的子節(jié)點個數(shù)。

對于每個節(jié)點x，我們選擇其子節(jié)點y，使得size[y]>=size[z](z為x的任意子節(jié)點)。

此時x便有一條重邊指向y，多條輕邊指向其他子節(jié)點。上圖：

如圖，用黑線連接的結點都是重結點，其余均是輕結點，

2-11就是重鏈，2-5就是輕鏈，用紅點標記的就是該結點所在重鏈的起點，也就是下文提到的top結點，

同時我們可以觀察到：

1. 對于任意一個結點的輕兒子，這個輕兒子是另一條重鏈的開頭。即除根節(jié)點以外的重鏈開頭的父結點都在重鏈上。

2. 不在重鏈上的葉子節(jié)點獨自構成一條重鏈（但寫題時不要葉子結點的重兒子設為自己，會引起不必要的麻煩）。

所以輕鏈本質上就是用來連接不同的重鏈的。在清楚輕重鏈的定義之后，我們就可以開始進行一些神（xuan）奇（xue）的操作了——

先定義以下幾個數(shù)組：

• siz[i]=j：節(jié)點i的子樹個數(shù)為j

• son[i]=j：節(jié)點i的重鏈指向j

• top[i]=j：節(jié)點i所在的重鏈開頭為j

• dep[i]=j：節(jié)點i的深度為j

• fa[i]=j：節(jié)點i的父親節(jié)點為j

首先進行初始化，這個過程需要兩個dfs進行。

第一個dfs，初始化siz、fa、dep、son數(shù)組：

第二個dfs，利用剛剛的fa、son數(shù)組初始化top數(shù)組：

然后，我們通過觀察推理可以得出：

• 若詢問的兩個節(jié)點x，y在同一條重鏈上，那么深度較小的那個點就是我們要求的公共祖先。

若不在同一條重鏈上呢？

• 我們可以直接跳到x、y所在重鏈的開頭的父親fx和fy，然后比較fx和fy的深度。若fx<fy，就讓y跳到fy的位置，反之亦然。

這樣一來，我們就可以不斷向上跳到新的重鏈上，直到這兩個節(jié)點在同一重鏈上（最壞情況就都跳到根節(jié)點上唄）

以上就是利用樹剖實現(xiàn)LCA聽說常數(shù)比倍增小

以下是全部代碼：

玄學玩意總算完了

本質上樹剖也是暴力優(yōu)化，類似隔壁的分塊，但時間復雜度還是挺優(yōu)秀的（聽說還能加上線段樹用）

完結撒波奇醬~

祈愿心海和崩崩小圓帽