已找到重心數（centroidsFound）：0
紅色為正在算子樹大小/沿路檢查是否為重心的節點；綠色（粗框）為剛選定的重心；灰暗為已移除的重心；節點上方數字為當前這一輪（pass）的子樹大小。
想像一棵有幾十萬個節點的大樹,你要反覆問「A 到 B 這條路上加起來是多少」或「離某個點幾步內有幾個節點」,每次都從頭爬一遍太慢。 這頁的兩招都是同一個念頭:先把大樹拆成好管理的小塊,之後查詢就變快。重心分解像每次都從最平衡的支點把樹對半折, 折沒幾層,任兩點都能靠少數幾個支點接起來;樹鏈剖分則像把樹上的路歸成幾條主幹道,走任何一段路最多只換幾條幹道。 下面兩欄讓你並排看它們怎麼一步步把同一棵樹拆開。
以下兩種是樹上問題常用、但方向不同的「分解」技術：重心分解（Centroid Decomposition）反覆在目前連通塊中找重心（移除後各子塊大小皆 ≤ 塊大小一半）， 標記移除並對每個子塊遞迴，建出一棵深度 O(log n) 的重心分解樹，適合樹上路徑類問題的分治； 樹鏈剖分（Heavy-Light Decomposition，HLD）則用兩階段 DFS 選出每個節點的「重兒子」（子樹最大的孩子）、 分配連續 DFS 序，把整棵樹拆成 O(log n) 條「重鏈」，任意路徑最多跨越 O(log n) 段連續區間，適合搭配線段樹做路徑查詢/更新。 兩者都靠子樹大小驅動，但一個是「反覆減半」、一個是「按重兒子剖分成鏈」。
對目前未移除節點構成的連通塊：先以任一節點為起點算出各節點子樹大小，再從起點出發，只要有鄰居的子樹大小 > 塊大小一半就往該鄰居移動， 直到無法移動即為此塊的重心；標記重心已移除、記錄其在重心分解樹中的父節點，再對每個未移除的鄰居子塊遞迴。 每次移除的重心保證各子塊大小 ≤ 原大小一半，故遞迴深度為 O(log n)。
兩階段 DFS：dfs1 後序算出每個節點的子樹大小，並在回溯時選出子樹最大的孩子為「重兒子」（同大小時保留先出現、即 id 較小者）； dfs2 從根出發優先走訪重兒子、分配連續的 DFS 序 pos，同一條重鏈上的節點共用同一個 chainTop（鏈頂）， 每個「輕兒子」則自成一條新鏈（chainTop = 自己）。重鏈在圖上以綠色粗邊持續累積顯示。