HDU 5148 Cities：樹形 DP 最小化邊權經過次數

問題描述

給定一棵帶權樹，需選擇 K 個節點，使得所有選中節點兩兩之間的路徑上，每條邊被經過的次數乘以其權值之和最小。輸出最小總代價。

DP 狀態定義

dp[u][j] 表示以 u 為根的子樹中選 j 個節點的最小代價。合併子樹時，邊 u-v 的貢獻為 w * (K - j) * j，其中 j 為子樹 v 選取的節點數，K-j 為其餘部分選取的節點數，兩兩配對經過該邊。

狀態轉移

dp[u][k+j] = min(dp[u][k+j], dp[u][k] + dp[v][j] + 2*w * (K-j) * j)

注意邊權乘 2（往返），且為優化採用滾動數組逆序更新 k。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
const long long INF = -1;
int N, K;
long long ans, dp[MAXN][55];
vector<pair<int,int>> g[MAXN];

void cmin(long long &v, long long x) { if (v == -1 || v > x) v = x; }

void dfs(int u, int fa) {
    dp[u][1] = 0;
    for (auto [v, w] : g[u]) if (v != fa) {
        dfs(v, u);
        w *= 2;
        for (int k = K-1; k >= 1; --k) if (dp[u][k] != -1)
            for (int j = 1; j + k <= K; ++j) if (dp[v][j] != -1)
                cmin(dp[u][k+j], dp[u][k] + dp[v][j] + w * (K - j) * j);
    }
    if (dp[u][K] != -1) cmin(ans, dp[u][K]);
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &K);
        ans = -1;
        fill(&dp[0][0], &dp[0][0] + sizeof(dp)/sizeof(long long), -1);
        for (int i = 1; i <= N; ++i) g[i].clear();
        for (int i = 1; i < N; ++i) {
            int a, b, c; scanf("%d%d%d", &a, &b, &c);
            g[a].emplace_back(b, c);
            g[b].emplace_back(a, c);
        }
        dfs(1, 0);
        printf("%lld\n", ans);
    }
    return 0;
}

關鍵技巧

1. 樹形 DP 背包合併：子樹大小限制合併上界
2. 邊貢獻公式推導：組合數意義的 (K-j)*j
3. 初始化 -1 表示不可達，cmin 輔助函數簡化更新邏輯

此題是樹形 DP 中「邊權貢獻分攤」的經典範例，掌握其合併邏輯對解決類似問題至關重要。