樹上的路徑問題很難直接用陣列或線段樹處理；重心分解把「隨便兩點之間的路徑」變成「一定經過某個特定節點的路徑」。
樹的重心
移除某個節點後，剩下的每個連通子樹大小都 ≤ n/2——這個節點就是樹的重心。
1
/ \
2 3
/ \ \
4 5 6
n = 6，移除節點 1：
子樹 {2,4,5}（大小 3）、{3,6}（大小 2）
最大子樹 3 ≤ 6/2 = 3 ✓ → 節點 1 是重心重心的保證：每棵樹至少有一個重心，且找重心只需 O(n)（先算子樹大小，找滿足條件的節點）。
分解過程
1. 找當前樹的重心 c
2. 統計「所有經過 c 的路徑」
3. 移除 c（標記 removed[c] = true）
4. 對剩下的每個子樹遞迴重複
遞迴深度：每次移除重心後，每個子樹大小 ≤ n/2
→ 至多 log n 層，每層 O(n)，總 O(n log n)路徑統計（長度 ≤ k 的路徑數量）
long countPaths(int root, int k) {
int c = findCentroid(root, subtreeSize[root]);
removed[c] = true;
List<Long> allDist = new ArrayList<>();
allDist.add(0L); // 從 c 出發的路徑（c 本身）
long count = 0;
for (int child : adj[c]) {
if (removed[child]) continue;
List<Long> childDist = getDistances(child, c, 1);
// 統計「一端在 child 子樹，一端在已處理子樹」且距離 ≤ k 的路徑
count += countPairs(allDist, childDist, k);
allDist.addAll(childDist);
}
// 遞迴處理每個子樹
for (int child : adj[c])
if (!removed[child])
count += countPaths(child, k);
return count;
}⚠️ 上面
findCentroid(root, subtreeSize[root])為了精簡直接沿用了一開始算好的subtreeSize陣列，但實務上不能這樣：移除重心後各子樹的大小會整個改變，每一層遞迴都要重算 subtree size（進countPaths先跑一次 DFS 重算當前子樹的大小），拿舊的整棵樹的 size 去找重心會找錯。
countPairs(A, B, k)：統計 a∈A, b∈B 且 a+b ≤ k 的對數。排序 A，對 B 中每個 b 二分搜尋，O((|A|+|B|) log n)。
容斥補正：直接統計 allDist 會算到「兩端都在同一個子樹」的路徑，通過分批統計（先統計、再加入 childDist）避免重複。
重心分解樹（Centroid Tree）
把每個重心作為父節點，子節點是它移除後各子樹的重心，形成「重心分解樹」。
重心分解樹高度 O(log n)，任意節點到根路徑上的節點集合代表「原樹中包含這個節點的所有重心」——對每個重心做統計，等效於覆蓋所有路徑。
這棵樹還能拿來查距離。任兩點 u、v 在重心分解樹上的最近公共祖先，就是原樹上「u→v 路徑一定會經過」的那一層重心，於是：
dist(u, v) = dist(u, 最近公共重心) + dist(v, 最近公共重心)預處理各層重心到子樹各點的距離後，單次距離查詢降到 O(log n)——重心分解樹的高度只有 log n，是這一切能成立的關鍵。
複雜度
| 操作 | 複雜度 |
|---|---|
| 建重心分解樹 | O(n log n) |
| 路徑計數（長度 ≤ k） | O(n log n) |
| 距離查詢（預處理後） | O(log n) |
🎬 互動視覺化：樹分解兩招並排看 — 一層層剝掉重心、看子樹如何減半，順便和樹鏈剖分的「切鏈」對照，兩種拆樹思路差在哪一目了然。
重心分解的直覺是：任何兩點路徑都必須經過某一層的重心——找到這一層，問題就分解了。
接下來往哪走
- 樹鏈剖分 HLD：把樹上路徑轉成線段樹區間 — 下一篇：樹上演算法四部曲第三部，另一種拆樹方式
- Binary Lifting：O(log n) 跳祖先、找 LCA — 路徑長度計算需要的 LCA 工具在這裡
- Divide and Conquer 分治法 — 重心分解就是分治搬到樹上：切重心、各子樹遞迴