您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

UVALive 4015 Caves：樹形 DP 解決根節點距離限制下的最大訪問節點數

編輯：C++ 入門

問題描述

給定一棵 n 個節點的有根樹，邊權為正整數表示距離。從根節點出發，總路徑長度不超過 x，求最多能訪問多少個不同節點（重複經過只算一次）。需回答多組查詢。

核心思路：樹形動態規劃

定義 d[u][k][c] 表示以 u 為根的子樹中，訪問 k 個節點的最短距離，其中：

c = 0：最終返回 u
c = 1：最終不返回 u（即在某子樹中結束）

初始狀態：d[u][1][0] = d[u][1][1] = 0（只訪問 u 本身）。

對每個子節點 v（邊長 len），合併 DP 表：

若最終返回 u：需往返 v 子樹，距離增加 2 * len
若最終不返回 u：兩種情況
- 在 v 子樹不返回，其餘子樹返回：d[u][j][1] + d[v][k][0] + len
- 在 v 子樹返回，其餘子樹不返回：d[u][j][0] + d[v][k][1] + 2 * len

C++ 實現要點

const int MAXN = 550;
int d[MAXN][MAXN][2];
int son[MAXN];
vector> g[MAXN]; // {子節點, 邊長}

void dfs(int u) {
    for (int i = 1; i <= n; ++i) d[u][i][0] = d[u][i][1] = INF;
    d[u][1][0] = d[u][1][1] = 0;
    son[u] = 1;

    for (auto [v, len] : g[u]) {
        dfs(v);
        for (int j = son[u]; j >= 1; --j) {
            for (int k = 1; k <= son[v]; ++k) {
                // 最終返回 u
                d[u][j+k][0] = min(d[u][j+k][0],
                    d[u][j][0] + d[v][k][0] + 2*len);
                // 最終不返回 u
                d[u][j+k][1] = min(d[u][j+k][1],
                    min(d[u][j][0] + d[v][k][1] + len,
                        d[u][j][1] + d[v][k][0] + 2*len));
            }
        }
        son[u] += son[v];
    }
}