Centroid Decomposition 重心分解

演算法說明

Centroid Decomposition 每次找到當前子樹的重心，以它為根，遞迴處理所有子樹。

• 重心定義：移除後，所有剩餘子樹大小都 ≤ n/2
• 深度保證：分解樹深度 ≤ log₂(n)，因為每次移除重心後子樹大小至少減半
• 路徑問題：任何路徑 u→v 必定經過某一層的重心 → 在 O(log n) 層逐層處理
• 典型應用：統計長度 ≤ k 的路徑數量、樹上距離查詢
• 複雜度：O(n log n) 建樹，O(log n) 查詢