POJ 3107 Godfather：樹的重心完整求解與 C++ 實現

問題背景

在圖論中，「樹的重心」是指刪除該節點後，剩餘各連通塊的節點數最大值最小的節點。一棵樹可能有一個或兩個重心。POJ 3107 要求找出所有重心並按編號輸出。

核心思路

對每個節點 u，計算其作為根時各子樹的大小 sum[v]，以及「上方部分」的大小 n - sum[u]。節點 u 的最大連通塊大小為：
max( max_child_sum, n - sum[u] )
其中 max_child_sum 為所有子樹大小的最大值。遍歷所有節點，記錄全局最小值 min1，並收集所有達到該值的節點。

算法步驟

1. 用鄰接表存儲樹（無向圖）。
2. 從任意節點（如 1）出發 DFS，計算每個節點的子樹大小 sum[u] 並同步更新最大連通塊大小。
3. 維護全局最小值 min1 與結果數組 ans[]。
4. 輸出所有重心節點編號。

關鍵代碼片段

void dfs(int u, int fa) {
    int max1 = 0, tot = 0;
    sum[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa) continue;
        dfs(v, u);
        sum[u] += sum[v];
        max1 = max(max1, sum[v]);
        tot += sum[v];
    }
    max1 = max(max1, n - tot - 1); // 上方部分大小
    if (min1 > max1) {
        min1 = max1; num = 0; ans[num++] = u;
    } else if (min1 == max1) {
        ans[num++] = u;
    }
}

複雜度分析

時間複雜度 O(N)，空間複雜度 O(N)，N ≤ 50000 完全滿足要求。

常見坑點

• 遞歸深度可能超過棧限制，建議加上 #pragma comment(linker, "/STACK:1024000000") 或改用非遞歸 DFS。
• 輸入包含多組測試數據，需循環讀取直到 EOF。
• 節點編號從 1 開始，數組大小開 MAXN<<1 防止邊數溢出。