樹上的路徑問題很難直接用陣列或線段樹處理；重心分解把「隨便兩點之間的路徑」變成「一定經過某個特定節點的路徑」。
樹的重心
移除某個節點後，剩下的每個連通子樹大小都 ≤ 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;
}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)，任意節點到根路徑上的節點集合代表「原樹中包含這個節點的所有重心」——對每個重心做統計，等效於覆蓋所有路徑。
重心分解的直覺是：任何兩點路徑都必須經過某一層的重心——找到這一層，問題就分解了。