Ural 1039 Anniversary Party 詳解

題目：樹狀組織結構（根為校長），N (≤6000) 員工，每人有「歡樂度」（-128~127）。選擇參加派對的人員，限制：員工與其直接上司不能同時參加。最大化總歡樂度。

核心模型：樹形 DP 獨立集

對每個節點 u，定義：
dp[u][0]：u 不參加時，以 u 為根的子樹最大歡樂度。
dp[u][1]：u 參加時，以 u 為根的子樹最大歡樂度。

狀態轉移

• u 不參加：子節點可參加可不參加，取最大。
  dp[u][0] = Σ max(dp[v][0], dp[v][1])，v 為 u 的孩子。
• u 參加：子節點必須不參加。
  dp[u][1] = Σ dp[v][0] + happy[u]。

葉節點：dp[u][0]=0, dp[u][1]=happy[u]。
答案：max(dp[root][0], dp[root][1])。

尋找根節點

輸入給出邊 L K 表示 K 是 L 的上司。統計入度，入度為 0 的即為根。

參考代碼 (C++)

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

const int MAXN = 6005;
int happy[MAXN];
vector children[MAXN];
int dp[MAXN][2];
bool hasParent[MAXN];

void dfs(int u) {
    dp[u][0] = 0;
    dp[u][1] = happy[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() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) {
            cin >> happy[i];
            children[i].clear();
            hasParent[i] = false;
        }
        int l, k;
        while (cin >> l >> k) {
            if (l == 0 && k == 0) break;
            children[k].push_back(l);
            hasParent[l] = true;
        }
        int root = 1;
        while (hasParent[root]) ++root;
        dfs(root);
        cout << max(dp[root][0], dp[root][1]) << '\n';
    }
    return 0;
}

關鍵細節

• 遞歸深度：N≤6000，遞歸可能棧溢出，建議改用迭代後序遍歷或增大棧（競賽環境通常足夠）。
• 負歡樂度：DP 自然處理，不選可能更優。
• 多測試用例：輸入以 EOF 結束，while(cin>>n)。
• 初始化：每測試用例清空 children、hasParent。

複雜度分析

總結

Ural 1039 是「樹上最大權獨立集」的標準 DP 題。狀態定義清晰（選/不選），轉移邏輯直接體現約束條件。此模式廣泛適用於「無相鄰選擇最大權和」問題：如房屋偷盜 (LeetCode 198/213/337)、課程選擇衝突、無線網絡信道分配等。