BZOJ 2286 SDOI 2011 消耗戰：虛樹 + 樹形 DP + LCA 倍增

問題描述

給一棵有根樹（根 1），邊有權。Q 次查詢，每次給 k 個關鍵點。需刪除一些邊，使根與所有關鍵點斷開，最小化刪除邊權和。Σk ≤ O(n)。

核心思想：虛樹（關鍵點重建樹）

每次查詢只涉及少量關鍵點，若在整棵樹上 DP 會 O(nQ) 過慢。
構建虛樹：只包含關鍵點及其 LCA，邊權為原樹路徑上最小邊權。
虛樹邊數 = O(k)，所有查詢總邊數 = O(Σk) = O(n)。

虛樹構建（單調棧 + DFS 序）

1. 預處理：DFS 求 dfn（進入時間）、depth、倍增祖先 fa[u][i]、minEdge[u][i]（向上 2^i 邊最小權）。
2. 關鍵點按 dfn 排序。
3. 維護單調棧（棧中節點按深度遞增，構成一條鏈）。
   新節點 u 入棧：
     lca = LCA(u, stack.top)。
     若 lca 深度 < 棧頂深度，彈出棧頂並連邊（棧頂→次棧頂），直到 lca 深度 ≥ 棧頂深度。
     若 lca ≠ 棧頂，壓入 lca。
     壓入 u。
   最後將棧中剩餘節點依次連邊。

樹形 DP 求解

在虛樹上從根（1）遞歸：
f(u) = sum_{v 子節點} min(f(v), minEdge(u,v))
若 u 是關鍵點，則必須切斷與父邊（或子邊），即 f(u) = INF（葉子關鍵點返回 INF，父節點 min 時會選擇切邊權）。
實際代碼中用 is_key[u] 標記，DP 時若為關鍵點則返回 INF。

代碼實現 (C++ 關鍵片段)

// 倍增預處理
void dfs(int u, int p) {
    dfn[u] = ++timer; dep[u] = dep[p] + 1; fa[u][0] = p;
    for (auto [v, w] : tree[u]) if (v != p) {
        minE[v][0] = w;
        dfs(v, u);
    }
}
void build_lca() {
    for (int j = 1; j < LG; ++j)
        for (int i = 1; i <= n; ++i) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
            minE[i][j] = min(minE[i][j-1], minE[fa[i][j-1]][j-1]);
        }
}
// LCA + 路徑最小邊
int lca(int u, int v) { ... }
int get_min(int u, int v) { ... }
// 虛樹構建 + DP
long long dp(int u) {
    long long sum = 0;
    for (int v : vtree[u]) {
        sum += min(dp(v), get_min(u, v));
    }
    return is_key[u] ? INF : sum;
}

複雜度

• 預處理：O(n log n)。
• 每查詢：O(k log k) 排序 + O(k) 虛樹構建 + O(k) DP。總 O(Σk log k) = O(n log n)。

關鍵點

• 虛樹將大樹問題壓縮為關鍵點子樹，總複雜度線性於關鍵點總數。
• 單調棧維護 DFS 序下的鏈結構，構建虛樹邊。
• 倍增同時求 LCA 和路徑最小邊權。

這是「樹上查詢 + 關鍵點子集」的經典虛樹模板，SDOI 2011 此題為虛樹技術的標志性應用。