BZOJ 3611 HEOI 2014 大工程：虛樹 + 樹形 DP 求關鍵點兩兩距離和/最小/最大

問題描述

給一棵樹（n ≤ 10⁶），m 次查詢 (m ≤ 5×10⁴)，每次給 k 個關鍵點 (Σk ≤ 2n)。求這 k 點之間：
1. 兩兩距離和。
2. 最小距離。
3. 最大距離。

虛樹構建（同 BZOJ 2286）

• 預處理：DFS 序、深度、倍增祖先。
• 關鍵點按 DFS 序排序，單調棧構建虛樹，邊權 = 原樹距離（深度差）。

虛樹上 DP 狀態

對每個節點 u 維護：
- cnt[u]：子樹內關鍵點數。
- sumDist[u]：子樹內關鍵點到 u 的距離和。
- maxD[u]：子樹內關鍵點到 u 的最大距離。
- minD[u]：子樹內關鍵點到 u 的最小距離（關鍵點為 0，非關鍵點初 INF）。

合併子節點 v 到 u（邊長 w）：
- 距離和貢獻：sumDist[u]*cnt[v] + sumDist[v]*cnt[u] + cnt[u]*cnt[v]*w。
- 最小距離：min(minD[u], minD[v] + w)（需考慮跨子樹：minD[u] + minD[v] + w）。
- 最大距離：類似，取 max。
- 更新 cnt[u] += cnt[v], sumDist[u] += sumDist[v] + cnt[v]*w, maxD[u] = max(maxD[u], maxD[v]+w), minD[u] = min(minD[u], minD[v]+w)。
全局答案在合併時累加更新。

代碼邏輯 (C++ 核心)

struct VTree {
    vector adj[MAXN];
    long long cnt[MAXN], sumD[MAXN], maxD[MAXN], minD[MAXN];
    bool isKey[MAXN];
    long long ansSum, ansMin, ansMax;
    void dp(int u) {
        cnt[u] = isKey[u];
        sumD[u] = 0;
        maxD[u] = isKey[u] ? 0 : -INF;
        minD[u] = isKey[u] ? 0 : INF;
        for (int v : adj[u]) {
            int w = depth[v] - depth[u]; // 原樹距離
            dp(v);
            // 更新全局答案
            ansSum += (sumD[u] + cnt[u]*w) * cnt[v] + sumD[v] * cnt[u];
            ansMin = min(ansMin, minD[u] + minD[v] + w);
            ansMax = max(ansMax, maxD[u] + maxD[v] + w);
            // 合併
            cnt[u] += cnt[v];
            sumD[u] += sumD[v] + cnt[v]*w;
            maxD[u] = max(maxD[u], maxD[v] + w);
            minD[u] = min(minD[u], minD[v] + w);
        }
    }
};

複雜度

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

關鍵點

• 虛樹將大樹壓縮為關鍵點子樹，DP 狀態設計巧妙聚合距離信息。
• 距離和合併公式推導：每對跨子樹點對距離 = (到 u 距離) + (到 v 距離) + w。
• 最小/最大距離需考慮跨子樹情況，在合併瞬間用兩子樹的極值更新全局答案。

這是虛樹 DP 的進階應用，同時維護多種聚合信息（和/最小/最大），展示了虛樹技術的強大通用性。