HDU 1520 Anniversary Party：樹形 DP (鏈式前向星優化)

題目大意

同 POJ 2342，但數據範圍 N ≤ 6000，測試用例多，vector 可能 TLE。需用**靜態鏈式前向星**存圖，遞歸 DFS 並注意棧大小。

鏈式前向星存圖

struct Edge { int to, next; } e[MAXN * 2];
int head[MAXN], ecnt;

void addEdge(int u, int v) {
    e[ecnt] = {v, head[u]};
    head[u] = ecnt++;
}

完整代碼 (C++)

#include 
#include 
#include 
using namespace std;

const int MAXN = 6005;
struct Edge { int to, next; } e[MAXN * 2];
int head[MAXN], ecnt;
int dp[MAXN][2], val[MAXN];
bool hasFather[MAXN];
int n, root;

void addEdge(int u, int v) {
    e[ecnt] = {v, head[u]};
    head[u] = ecnt++;
}

void dfs(int u) {
    dp[u][1] = val[u];
    dp[u][0] = 0;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        dfs(v);
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
}

int main() {
    while (~scanf("%d", &n)) {
        ecnt = 0;
        memset(head, -1, sizeof(head));
        memset(hasFather, 0, sizeof(hasFather));
        for (int i = 1; i <= n; i++) scanf("%d", &val[i]);
        for (int i = 0; i < n-1; i++) {
            int L, K; scanf("%d%d", &L, &K);
            addEdge(K, L); // K 是上司
            hasFather[L] = true;
        }
        root = 1;
        while (hasFather[root]) root++;
        dfs(root);
        printf("%d\n", max(dp[root][0], dp[root][1]));
    }
    return 0;
}

優化要點

• 靜態數組 `e[MAXN*2]` 替代 `vector`，避免動態分配開銷。
• `memset(head, -1, ...)` 初始化鏈表頭。
• 遞歸深度最多 6000，默認棧通常足夠 (Linux 8MB)；若 RE 可加編譯選項 `-Wl,--stack=268435456` (256MB) 或改寫迭代 DFS。
• 輸入以 EOF 結束，多測試用例循環。

與 POJ 2342 對比