HDU 1520 Anniversary Party：樹形 DP 求最大活躍度

問題描述

公司層級結構為樹，每個員工有活躍度（可負）。選擇一組員工參加派對，限制：員工與其直接上司不能同時參加。求最大活躍度和。

解題思路

樹形 DP：`dp[u][0]` 表示 u 不參加時子樹最大和，`dp[u][1]` 表示 u 參加時最大和。轉移：

• `dp[u][1] = val[u] + Σ dp[v][0]` （子女必須不參加）
• `dp[u][0] = Σ max(dp[v][0], dp[v][1])` （子女可參加或不參加）

從葉子向根 DFS 計算，根節點答案為 `max(dp[root][0], dp[root][1])`。樹以總經理為根，輸入給出邊 (L K) 表示 K 是 L 的上司。

代碼實現 (C++)

#include 
using namespace std;
const int MAXN = 6005;
struct Node { int val, child, brother, fa; } tree[MAXN];
int dp[MAXN][2];

void dfs(int u) {
    dp[u][1] = tree[u].val;
    dp[u][0] = 0;
    for (int v = tree[u].child; v; v = tree[brother]) {
        dfs(v);
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
}

int main() {
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) {
            tree[i].child = tree[i].brother = tree[i].fa = 0;
            cin >> tree[i].val;
        }
        int L, K;
        while (cin >> L >> K && (L || K)) {
            tree[L].fa = K;
            tree[L].brother = tree[K].child;
            tree[K].child = L;
        }
        int root = 1;
        while (tree[root].fa) root = tree[root].fa;
        dfs(root);
        cout << max(dp[root][0], dp[root][1]) << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n)。
• 空間複雜度：O(n)。

總結

經典的「最大獨立集」在樹上，樹形 DP 兩狀態轉移簡潔高效。兄弟鏈表存儲樹結構節省空間，遞歸 DFS 實現直觀。