USACO 2015 Dec Gold - Max Flow：樹上路徑增量查詢的重鏈剖分與線段樹解法

問題描述

給定一棵 N 個節點的樹 (N ≤ 50,000)，初始所有節點權值為 0。進行 K 次操作 (K ≤ 100,000)，每次指定兩節點 s, t，將 s 到 t 路徑上所有節點權值 +1。求最終權值最大的節點值。

核心挑戰

• 樹上路徑更新：任意兩點間路徑非線性
• 大規模數據：N 5萬、K 10萬，O(NK) 暴力不可行
• 需要 O((N+K) log N) 或更優解法

解法：重鏈剖分 + 線段樹

重鏈剖分 (Heavy-Light Decomposition)

將樹分解為若干重鏈，使任意路徑最多跨越 O(log N) 條重鏈。

// 關鍵陣列
int fa[maxn][20];     // 倍增 LCA：fa[u][i] 為 u 的 2^i 祖先
int dep[maxn];        // 深度
int siz[maxn];        // 子樹大小
int son[maxn];        // 重兒子
int top[maxn];        // 所在重鏈頂點
int dfn[maxn], rnk[maxn]; // DFS 序與反查
int tim = 0;

兩遍 DFS 建立剖分

// DFS1：計算大小、深度、重兒子、倍增祖先
void dfs1(int u, int f) {
    fa[u][0] = f;
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    for (int i = 1; i < 20; i++) 
        fa[u][i] = fa[fa[u][i-1]][i-1];
    
    for (int v : adj[u]) if (v != f) {
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
}

// DFS2：分配 DFS 序、確定重鏈頂點
void dfs2(int u, int tp) {
    top[u] = tp;
    dfn[u] = ++tim;
    rnk[tim] = u;
    if (son[u]) dfs2(son[u], tp);  // 重邊優先，保持連續
    for (int v : adj[u]) if (v != fa[u][0] && v != son[u])
        dfs2(v, v);  // 輕邊另起鏈
}

LCA 查詢 (倍增法)

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    // 提升 u 到同深度
    for (int i = 19; i >= 0; i--)
        if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    if (u == v) return u;
    // 同時跳躍
    for (int i = 19; i >= 0; i--)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

線段樹支援區間加、查詢最大值

struct Node {
    int l, r, mx, tag;  // 區間 [l,r], 最大值, 惰性標記
} t[maxn * 4];

void pushup(int k) { t[k].mx = max(t[k<<1].mx, t[k<<1|1].mx); }
void apply(int k, int v) { t[k].mx += v; t[k].tag += v; }
void pushdown(int k) {
    if (t[k].tag) {
        apply(k<<1, t[k].tag);
        apply(k<<1|1, t[k].tag);
        t[k].tag = 0;
    }
}

void update(int k, int l, int r, int v) {  // 區間加 v
    if (t[k].l == l && t[k].r == r) { apply(k, v); return; }
    pushdown(k);
    int mid = (t[k].l + t[k].r) >> 1;
    if (r <= mid) update(k<<1, l, r, v);
    else if (l > mid) update(k<<1|1, l, r, v);
    else { update(k<<1, l, mid, v); update(k<<1|1, mid+1, r, v); }
    pushup(k);
}

路徑分解更新

// 將 u 到祖先 v (v 是 u 祖先) 路徑上所有節點 +1
void path_add(int u, int v) {
    while (top[u] != top[v]) {
        update(1, dfn[top[u]], dfn[u], 1);
        u = fa[top[u]][0];  // 跳到重鏈頂點的父親
    }
    update(1, dfn[v], dfn[u], 1);  // 同一重鏈內
}

// 處理單次查詢 (s, t)
int w = lca(s, t);
path_add(s, w);
path_add(t, w);
update(1, dfn[w], dfn[w], -1);  // LCA 被加了兩次，減一

完整複雜度分析

總複雜度：O((N + K) log² N) ≈ 10⁵ × 16² ≈ 2.5×10⁷ 操作，輕鬆通過

關鍵細節與避坑

1. LCA 重複計算：路徑 s→w 和 t→w 都包含 w，需額外 -1 修正
2. DFS 序連續性：重鏈節點在線段樹中必須連續，dfs2 先遞歸重兒子
3. 陣列大小：線段樹 4×N，邊表 2×N，倍增 20×N (log₂50000 < 16)
4. 遞歸深度：N=50000 可能爆棧，建議改迭代或加大棧

模板代碼骨架

#include 
using namespace std;
const int maxn = 50005;
int n, m, ...;
// 圖、重鏈剖分、線段樹、LCA 相關陣列與函數
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; add_edge(u, v); }
    dfs1(1, 0); dfs2(1, 1); build(1, 1, n);
    while (m--) {
        int s, t; cin >> s >> t;
        int w = lca(s, t);
        path_add(s, w); path_add(t, w);
        update(1, dfn[w], dfn[w], -1);
    }
    cout << t[1].mx << '\n';
    return 0;
}

延伸思考

• 若查詢改為「路徑最大值」而非「全域最大值」？→ 線段樹 query 改為路徑分解查詢
• 若需要支援子樹更新？→ DFS 序天然支援子樹區間操作
• 動態樹 (Link-Cut Tree) 可支援連接/切斷邊的動態場景