HDU 1520 Anniversary Party：樹形 DP 經典入門（最大權獨立集）

問題轉化

公司層級結構 = 樹（根 = 校長）。每員工有「活躍度」權重（可負）。選邀請名單，**不允許直屬上下級同時參加**。求最大權重和。
即：樹上**最大權獨立集**（Maximum Weight Independent Set on Tree）。

DP 狀態定義

• dp[u][0]：以 u 為根的子樹中，**不選 u** 時的最大權和。
• dp[u][1]：以 u 為根的子樹中，**選 u** 時的最大權和。

狀態轉移方程

對 u 的每個孩子 v（遞歸後已計算）：

dp[u][0] += max(dp[v][0], dp[v][1]);  // u 不選，v 可選可不選，取最優
dp[u][1] += dp[v][0];                 // u 選，v 必須不選

初始化：dp[u][1] = weight[u]，dp[u][0] = 0。

遞歸順序

後序遍歷（DFS）：先遞歸處理所有孩子，再計算當前節點。任意節點作根均可（樹無環）。

C++ 精簡實現

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 6005;
vector<int> g[MAXN];
int dp[MAXN][2];
int weight[MAXN];
int n;

void dfs(int u, int parent) {
    dp[u][1] = weight[u];
    dp[u][0] = 0;
    for (int v : g[u]) {
        if (v == parent) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) {
            g[i].clear();
            cin >> weight[i];
        }
        for (int i = 1; i < n; ++i) {
            int u, v; cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, 0);
        cout << max(dp[1][0], dp[1][1]) << "\n";
    }
    return 0;
}

關鍵點

• 無環樹：DFS 時傳遞 parent 避免回溯。
• 權重可負：dp[u][1] 初始為負值時，不選可能更優，轉移方程自然處理。
• 多測試用例：while(cin>>n) 讀至 EOF，每例清空圖與 DP 陣列。
• 空間優化：dp 可用 vector<array<int,2>> 或滾動陣列，但 n=6000 靜態陣列無壓力。

複雜度

• 時間 O(n)，每條邊訪問一次。
• 空間 O(n)。

擴展變體

總結

HDU 1520 是樹形 DP 入門「Hello World」。狀態定義直觀（選/不選）、轉移方程簡潔、代碼極短。掌握此模板，可秒殺「樹上無相鄰選擇最大權」「派對邀請」「監控安裝」等經典問題。核心思想：**將全局約束分解為局部子問題，通過根節點決策串聯子樹最優解**。