樹鏈剖分 HLD：把樹上路徑轉成線段樹區間

線段樹處理連續陣列；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)。

---

HLD 的精髓是 DFS2：讓重鏈連續分配 DFS 序，把樹的拓撲結構壓平成陣列，讓線段樹能接手。