POJ 3107 Godfather：樹型 DP 與向前星優化

問題背景

求樹的重心：選任一節點為根，統計各子樹節點數。對非根節點，其餘部分視為另一子樹（大小 = 總節點數 - 當前子樹節點數）。找出使最大子樹節點數最小的節點。

關鍵優化：手寫鏈表替代 vector

原用 vector 導致 TLE，改用靜態陣列模擬鏈表（向前星）後 500ms 通過。

核心程式碼

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define oo 1000000007
#define MAXN 50005
using namespace std;

struct Edge { int x, y, next; } line[MAXN*2];
int n, AnsNum, AnsData, ans[MAXN], _next[MAXN];
bool used[MAXN];

void addline(int x, int y, int m) {
    line[m].next = _next[x]; _next[x] = m;
    line[m].x = x; line[m].y = y;
}

int dfs(int x) {
    int MaxSub = 0, num = 0, t, k = _next[x];
    while (k) {
        if (!used[line[k].y]) {
            used[line[k].y] = true;
            t = dfs(line[k].y);
            MaxSub = max(t, MaxSub);
            num += t;
            used[line[k].y] = false;
        }
        k = line[k].next;
    }
    MaxSub = max(MaxSub, n - (num + 1));
    if (MaxSub == AnsData) ans[++AnsNum] = x;
    else if (MaxSub < AnsData) { AnsData = MaxSub; AnsNum = 0; ans[++AnsNum] = x; }
    return num + 1;
}

int main() {
    int i;
    while (~scanf("%d", &n)) {
        memset(_next, 0, sizeof(_next));
        for (i = 1; i < n; i++) {
            int x, y; scanf("%d%d", &x, &y);
            addline(x, y, i*2-1); addline(y, x, i*2);
        }
        memset(used, false, sizeof(used));
        AnsData = oo; used[1] = true; dfs(1);
        sort(ans+1, ans+1+AnsNum);
        printf("%d", ans[1]);
        for (i = 2; i <= AnsNum; i++) printf(" %d", ans[i]);
        printf("\n");
    }
    return 0;
}

心得

競賽編程中，vector 擴容與記憶體分配開銷大，靜態鏈表效能更穩定。