重心剖分

Centroid Decomposition 施工中

樹重心

樹重心 (Centroid)：以樹重心為根時可以讓最多點的子樹點數最小，且這個值不超過 $\lfloor \frac{N}{2} \rfloor$

性質

1. 一顆樹最多有兩顆重心，至少一顆

2. 樹重心到所有點的距離和是全部的點中最小的

3. 將兩棵樹相連，新樹的重心會在兩棵樹的重心路徑上

4. 在一棵樹增加/刪除一個葉子，重心只會偏移至多一格

找重心

先做一次 DFS 找到以每個點為根的所有子樹的 size。再做第二次 DFS，如果對於一個點 $x$，他存在任何一個小孩的子樹大小大於 $\lfloor \frac{N}{2} \rfloor$，那麼代表重心一定在那個小孩的子樹裡面。一直 DFS 下去直到沒有任何小孩的子樹大小大於 $\lfloor \frac{N}{2} \rfloor$，那麼那個點就是重心。

重心剖分

重心剖分又稱點分治

對於一個有根樹而言，如果想要分治的話那麼可以分成 1. 經過根的答案 2. 不經過根的答案。不經過根的答案就直接丟給子樹就好了，經過根的答案就要特別統計。而如果我們選取重心作為有根樹的根，那麼我們會發現這樣子的分治的深度最多會是 $O(\log N)$。於是如果找到答案的複雜度是 $T(N)$，那整體的分治複雜度就是 $O(T(N)\log N)$。

實作

CD 樹

如果把樹的重心拔掉，就會形成若干顆子樹，如果繼續把子樹的重心找出來然後跟原本的重心去建邊，可以形成一顆高度為 $O(\log N)$ 的一顆樹，我們叫他 CD 樹 (中國叫點分樹)。

性質

1. CD 樹任何一個點的子樹是連通的子圖

2. CD 樹上任兩點的 LCA 必定存在在原圖中這兩點的路徑中

CD 樹上的邊不一定會存在在原圖，要分清楚原圖跟 CD 樹的差別。

用途

1. 解決樹形狀不變的帶修改問題 (高度 $O(\log N)$ 可以直接暴力)

2. 多次求解路徑問題 (ex: 對於所有點都要找到某種資訊)