POJ 2342 Anniversary Party：樹形 DP 入門經典——最大獨立集權值和

POJ 2342 Anniversary Party：樹形 DP 求最大歡樂值邀請名單

問題描述

公司員工形成以校長為根的樹，每人有歡樂值（可負）。約束：員工與其直屬上司不能同時參加。求邀請名單的最大歡樂值和。N ≤ 6000。

樹形 DP 狀態定義

• dp[u][0]：以 u 為根的子樹中，不選 u 時的最大歡樂值
• dp[u][1]：選 u 時的最大歡樂值

狀態轉移

dp[u][0] = Σ max(dp[v][0], dp[v][1])  // 不選 u，子節點可選可不選
dp[u][1] = value[u] + Σ dp[v][0]       // 選 u，子節點必須不選

邊界與答案

• 葉節點：dp[u][0]=0, dp[u][1]=value[u]
• 任意節點作根（建無向邊），答案：max(dp[root][0], dp[root][1])

完整代碼 (C++)

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

const int N = 6005;
struct Edge { int to, next; } e[N*2];
int head[N], tot, dp[N][2], val[N];
bool vis[N];

void init() { memset(head, -1, sizeof(head)); tot = 0; }
void add(int u, int v) { e[tot] = {v, head[u]}; head[u] = tot++; }

void dfs(int u) {
    vis[u] = true;
    dp[u][0] = 0; dp[u][1] = val[u];
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (!vis[v]) {
            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)) {
        init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", &val[i]);
            vis[i] = false;
        }
        for (int i = 1; i < n; i++) {
            int u, v; scanf("%d%d", &u, &v);
            add(u, v); add(v, u);
        }
        int u, v; scanf("%d%d", &u, &v);  // 讀 0 0
        dfs(1);
        printf("%d\n", max(dp[1][0], dp[1][1]));
    }
    return 0;
}

複雜度

O(N) 時間，O(N) 空間。N=6000 瞬時通過。