HDU 1520 Anniversary Party：樹形 DP 最大快樂值獨立集

HDU 1520「Anniversary Party」：公司層級樹結構，每人有快樂值。選派參加派對的人員，要求直屬上下級不能同時參加。求最大總快樂值。本文解析經典樹形 DP 最大權獨立集模板。

問題建模

• 樹根為最高領導（無上級）。
• 每個節點 i 有權值 val[i]。
• 選擇節點子集，滿足：無邊的兩端點同時被選。即獨立集。
• 最大化權值和。

樹形 DP 狀態

dp[u][0] = 以 u 為根的子樹中，u 不選 時的最大權值。
dp[u][1] = 以 u 為根的子樹中，u 選 時的最大權值。

狀態轉移

遍歷 u 的所有孩子 v：

• u 不選：v 可選可不選，取最大。
  dp[u][0] += max(dp[v][0], dp[v][1])
• u 選：v 必須不選。
  dp[u][1] += dp[v][0]

遞歸實現

void dfs(int u) {
    dp[u][1] = val[u]; // 初始化：選 u 至少有自己的值
    for (int v : children[u]) {
        dfs(v);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

找根節點

輸入給出邊 (L, K) 表示 K 是 L 的上級。
統計所有節點的入度，入度為 0 的即為根。

完整代碼（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 6010;
vector children[MAXN];
int dp[MAXN][2];
int val[MAXN];
int indeg[MAXN];

void dfs(int u) {
    dp[u][1] = val[u];
    for (int v : children[u]) {
        dfs(v);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; ++i) {
            children[i].clear();
            indeg[i] = 0;
            scanf("%d", &val[i]);
            dp[i][0] = dp[i][1] = 0;
        }
        int l, k;
        while (scanf("%d%d", &l, &k) == 2 && (l || k)) {
            children[k].push_back(l);
            indeg[l]++;
        }
        int root = 1;
        while (indeg[root]) ++root;
        dfs(root);
        printf("%d\n", max(dp[root][0], dp[root][1]));
    }
    return 0;
}

複雜度

• 時間：O(n) — 每個節點訪問一次，每條邊處理一次。
• 空間：O(n) — 存圖、DP 表、遞歸棧。

關鍵細節

1. 多測試用例：每用例清空圖、入度、DP 數組。
2. 根節點查找：入度為 0。
3. 輸入結束：l=0, k=0 結束當前用例邊輸入。
4. 遞歸深度：n ≤ 6000，遞歸棧通常足夠，極端鏈狀樹可能棧溢出，可改迭代或增大棧。

總結

本題是「樹上最大權獨立集」的標準模板題。核心狀態 dp[u][0/1] 和轉移方程極其固定：

• dp[u][0] = Σ max(dp[v][0], dp[v][1])
• dp[u][1] = val[u] + Σ dp[v][0]

掌握此模板，可直接解決「樹上選點、相鄰不可同時選、最大化權值」等所有變體（如放衛兵、派對、獨立集計數等）。