SDOI 2011 消耗戰：虛樹優化樹形 DP 求最小切割成本

問題模型

樹上每條邊有切割成本。多次查詢，每次給定關鍵點集合，需切割邊使關鍵點兩兩不連通，最小化總成本。虛樹將無關節點壓縮，僅在關鍵點及其 LCA 上 DP。

虛樹構建流程

1. 關鍵點按 DFS 序排序
2. 棧維護右側鏈，遇到 LCA 彈棧連接
3. 邊權為原樹路徑上最小切割成本（或按題意定義）

DP 定義

dp[u]：以 u 為根的虛樹子圖中，分離所有關鍵點的最小成本。
mn[u]：u 到其子樹關鍵點路徑上的最小邊權（題目特定）。

轉移邏輯

ll dfs(u) {
    ll sum = 0;
    for (v : 虛樹子節點) sum += dfs(v);
    return sum ? min(sum, mn[u]) : mn[u];  // 葉子直接取 mn
}

關鍵優化

• INF 必須足夠大（如 1e18）防溢出
• 虛樹邊構建時按深度連接，保證父子關係正確
• 每次查詢後清空虛樹邾表（或用時間戳）

複雜度

預處理 O(n log n)，單查詢 O(k log k)，k 為關鍵點數。虛樹將 n 降為 O(k)，巨大優化。