POJ 2763 Housewife Wind：樹鏈剖分 + 線段樹維護路徑權值

題目大意

樹上 n 點，初始位置 s。兩類操作：
1) 0 u：查詢當前位置到 u 的路徑邊權和，並移動到 u。
2) 1 i w：修改第 i 條邊的權值為 w。
n, m ≤ 10⁵。

樹鏈剖分 (Heavy-Light Decomposition)

1. DFS1：計算子樹大小 sz[u]、深度 dep[u]、父節點 fa[u]、重兒子 son[u]（子樹最大）。
2. DFS2：按重鏈分解，分配 dfn[u]（DFS 序）、top[u]（重鏈頂點）。重兒子優先遞歸保證同一重鏈連續。
3. 線段樹：在 dfn 序上建樹，支持單點修改（邊權存儲在深度較深的端點 dfn 位置）、區間查詢和。

路徑查詢

query(u, v)：
while top[u] != top[v]：
 若 dep[top[u]] < dep[top[v]] swap。
 累加 seg.query(dfn[top[u]], dfn[u])。
 u = fa[top[u]]。
同一重鏈內：
 若 dep[u] > dep[v] swap。
 累加 seg.query(dfn[u]+1, dfn[v])（邊權不含 LCA 點）。

C++ 代碼框架

// 關鍵結構
struct Edge { int to, w, id, nxt; } e[MAXN*2];
int h[MAXN], cntE;
int sz[MAXN], dep[MAXN], fa[MAXN], son[MAXN], top[MAXN], dfn[MAXN], rnk[MAXN], tim;
int segVal[MAXN]; // dfn位置對應的邊權

// DFS1
void dfs1(int u, int f) {
    sz[u]=1; fa[u]=f; dep[u]=dep[f]+1;
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].to; if(v==f) continue;
        dfs1(v,u); sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v, edgeId[u]=e[i].id; // 記錄邊id
    }
}

// DFS2
void dfs2(int u, int tp) {
    top[u]=tp; dfn[u]=++tim; rnk[tim]=u;
    if(son[u]) dfs2(son[u], tp);
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].to; if(v==fa[u]||v==son[u]) continue;
        dfs2(v, v);
    }
}

// 線段樹單點修改、區間查詢和（標準模板）
// 主程序：讀入邊構建圖，dfs1(1,0), dfs2(1,1)，線段樹build
// 查詢0 u: ans=queryPath(cur, u); cur=u;
// 修改1 i w: 找到邊i對應的深節點v，seg.update(dfn[v], w);

關鍵細節

• 邊權存儲：第 i 條邊連接 u, v，權值存入 dfn[dep[u]>dep[v]?u:v]。
• 查詢路徑不含 LCA 點：同重鏈時查詢 [dfn[u]+1, dfn[v]]。
• 修改操作需知道邊對應的深節點，DFS1 時記錄 edgeId[u]。

總結

POJ 2763 是「樹鏈剖分 + 線段樹」的標準模板題。核心流程：兩次 DFS 分解重鏈 → 線段樹維護邊權 → 路徑拆解為 O(log²n) 區間查詢/修改。同模板解決 BZOJ 2243、Codeforces 樹上路徑查詢問題。