線段樹處理連續陣列；HLD 讓樹上的路徑也變成「連續的一段」。
為什麼需要 HLD？
樹上路徑查詢（路徑上所有節點的值的最大值、和）很常見，但樹的路徑不是陣列裡連續的元素——沒辦法直接套線段樹。
LCA 可以找到路徑，但一段段地取路徑上的節點仍是 O(n)。HLD 把樹預處理後，任意路徑在 DFS 序中最多只跨 O(log n) 個連續段，每段用線段樹 O(log n) 查詢，總 O(log² n)。
重邊與輕邊
對每個非葉節點 u：
重兒子（heavy child）= 子樹最大的孩子
重邊（heavy edge）= 連向重兒子的邊
輕邊（light edge）= 連向其他孩子的邊
重邊串起來形成重鏈（heavy chain）
每個節點恰好屬於一條重鏈為什麼路徑最多跨 O(log n) 條鏈？
沿輕邊往上走一步：子樹大小至少翻倍（輕兒子的子樹 ≤ 父子樹/2）。從任何節點到根，最多走 O(log n) 條輕邊，因此任意路徑最多跨 O(log n) 條重鏈。
兩次 DFS 預處理
// DFS1：計算子樹大小、深度、父節點、重兒子
void dfs1(int v, int par, int d) {
parent[v] = par; depth[v] = d; subtreeSize[v] = 1;
heavyChild[v] = -1;
int maxSize = 0;
for (int u : adj[v]) {
if (u == par) continue;
dfs1(u, v, d + 1);
subtreeSize[v] += subtreeSize[u];
if (subtreeSize[u] > maxSize) {
maxSize = subtreeSize[u];
heavyChild[v] = u;
}
}
}
// DFS2：分配 DFS 序（同一條重鏈連續）
void dfs2(int v, int top) {
chainTop[v] = top;
pos[v] = timer++; // 線段樹的位置
if (heavyChild[v] != -1)
dfs2(heavyChild[v], top); // 重兒子繼承同一條鏈
for (int u : adj[v]) {
if (u != parent[v] && u != heavyChild[v])
dfs2(u, u); // 輕兒子開啟新鏈，鏈頂是自己
}
}路徑查詢
int pathQuery(int u, int v) {
int result = 0;
while (chainTop[u] != chainTop[v]) {
// u 和 v 不在同一條鏈上
if (depth[chainTop[u]] < depth[chainTop[v]])
swap(u, v);
// 讓 u 的鏈頂更深（更靠下），先把 u 那條鏈查完
result = merge(result, segTree.query(pos[chainTop[u]], pos[u]));
u = parent[chainTop[u]]; // 跳到上一條鏈
}
// 現在 u, v 在同一條鏈，直接查詢
if (depth[u] > depth[v]) swap(u, v);
result = merge(result, segTree.query(pos[u], pos[v]));
return result;
}每次 while 循環把一條重鏈「消化掉」，最多 O(log n) 次，每次線段樹查詢 O(log n)，總 O(log² n)。
複雜度
| 操作 | 複雜度 |
|---|---|
| 預處理（兩次 DFS） | O(n) |
| 路徑查詢 / 更新 | O(log² n)（O(log n) 條鏈 × 每條線段樹 O(log n)） |
| 子樹查詢 / 更新 | O(log n) |
子樹查詢意外地便宜：一個節點的整棵子樹在 DFS 序裡剛好是一段連續區間（pos[v] 到 pos[v] + subtreeSize[v] - 1），線段樹一次就掃完，比路徑查詢還快一個 log。
HLD 該跟誰比？
樹上演算法四部曲各有守備範圍，別拿 HLD 去做它不擅長的事：
| HLD | Binary Lifting | 重心分解 | |
|---|---|---|---|
| 路徑查詢 + 更新 | O(log² n) | 不支援更新 | — |
| LCA | O(log n) | O(log n) | — |
| 路徑計數 | 難以直接支援 | — | O(n log n) |
| 主場 | 動態路徑查詢 | 靜態 LCA / 祖先 | 路徑統計 |
一句話分：要邊查邊改路徑上的值，選 HLD；只問祖先、不改值，Binary Lifting 更輕；數路徑、統計距離，重心分解。
🎬 互動視覺化：樹分解兩招並排看 — 看 DFS2 怎麼把重鏈壓平成連續 pos、路徑查詢又怎麼一條鏈一條鏈往上跳，和重心分解的拆法擺一起對照。
HLD 的精髓是 DFS2：讓重鏈連續分配 DFS 序，把樹的拓撲結構壓平成陣列，讓線段樹能接手。
接下來往哪走
- Tarjan 離線 LCA：一次 DFS 回答所有 LCA 查詢 — 下一篇：樹上演算法四部曲的最後一部
- Segment Tree 線段樹 — HLD 把路徑壓平之後，接手區間查詢的就是它
- Binary Lifting：O(log n) 跳祖先、找 LCA — 只要 LCA 不要路徑統計時，這個更輕量