HDU 5274 重溫：樹鏈剖分維護路徑異或查詢與修改

樹鏈剖分核心思想

將樹分解為若干條重鏈，每條重鏈在 DFS 序中連續。任意路徑 u→v 可分解為 O(log N) 段連續區間，配合線段樹支持路徑查詢/修改。

關鍵數組

• fa[u]：父節點
• dep[u]：深度
• siz[u]：子樹大小
• son[u]：重兒子（子樹最大的孩子）
• top[u]：所在重鏈的頂端節點
• dfn[u]：DFS 序編號

兩次 DFS 構建

// DFS1: 計算 siz, son, fa, dep
void dfs1(int u, int f) {
    fa[u]=f; siz[u]=1; dep[u]=dep[f]+1;
    for (int v: G[u]) if (v!=f) {
        dfs1(v,u); siz[u]+=siz[v];
        if (siz[v] > siz[son[u]]) son[u]=v;
    }
}
// DFS2: 分配 dfn, top
void dfs2(int u, int tp) {
    top[u]=tp; dfn[u]=++tot;
    if (son[u]) dfs2(son[u], tp);
    for (int v: G[u]) if (v!=fa[u] && v!=son[u])
        dfs2(v, v);
}

路徑查詢/修改

int queryPath(int u, int v) {
    int res = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u,v);
        res ^= segQuery(dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u,v);
    res ^= segQuery(dfn[u], dfn[v]);
    return res;
}

void updateNode(int u, int val) { // 單點修改
    segUpdate(dfn[u], val);
}

線段樹維護異或值

線段樹節點存儲區間異或和。單點修改直接更新葉子再上推。區間查詢異或合併左右結果。

對比 LCA+線段樹 方案

本題修改影響子樹，LCA+線段樹更簡潔；若修改為單點值變更，樹鏈剖分更自然。