POJ 1655 Balancing Act：樹形 DP 尋找樹的重心

問題建模

給定 N 節點樹，刪除某節點後，剩餘連通分支中最大節點數最小化。該節點即為樹的重心。輸出重心編號及其最大分支大小。

樹形 DP 兩遍 DFS 算法

第一遍 DFS：計算子樹大小

void dfs_size(int u, int parent) {
    sz[u] = 1;
    for (int v : adj[u]) if (v != parent) {
        dfs_size(v, u);
        sz[u] += sz[v];
    }
}

sz[u] = 以 u 為根的子樹節點數 (含自身)。

第二遍 DFS：計算每個節點的最大分支

對節點 u，刪除後分支有兩類：

1. 子樹分支：每個孩子 v 對應分支大小 sz[v]
2. 父側分支：其餘部分，大小 N - sz[u]

void dfs_ans(int u, int parent) {
    int max_part = N - sz[u];  // 父側分支
    for (int v : adj[u]) if (v != parent) {
        dfs_ans(v, u);
        max_part = max(max_part, sz[v]);  // 子樹分支
    }
    if (max_part < best_val) {
        best_val = max_part;
        best_node = u;
    }
}

完整代碼 (鏈式前向星存圖)

#include 
#include 
#include 
using namespace std;

const int MAXN = 110000;
struct Edge { int to, next; } e[MAXN*2];
int head[MAXN], ecnt;
int sz[MAXN], N, best_val, best_node;

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

void dfs1(int u, int p) {
    sz[u] = 1;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
    }
}

void dfs2(int u, int p) {
    int mx = N - sz[u];
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == p) continue;
        dfs2(v, u);
        mx = max(mx, sz[v]);
    }
    if (mx < best_val) best_val = mx, best_node = u;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        memset(head, -1, sizeof(int)*(N+1));
        ecnt = 0;
        for (int i = 1; i < N; i++) {
            int a, b; scanf("%d%d", &a, &b);
            add_edge(a, b);
        }
        best_val = 0x3f3f3f3f;
        dfs1(1, 0);
        dfs2(1, 0);
        printf("%d %d\n", best_node, best_val);
    }
    return 0;
}

複雜度分析

• 時間：O(N) — 兩次 DFS 各訪問每條邊兩次
• 空間：O(N) — 鄰接表 + 遞歸棧 (深度可達 N，建議改迭代或增大棧)

關鍵優化點

1. 鏈式前向星：靜態數組存邊，無動態分配開銷，緩存友好
2. 全局變量：避免參數傳遞開銷，適配競賽環境
3. 雙向邊 + 父節點去重：無需建有向樹，簡化代碼
4. 初始化優化：memset(head, -1, ...) 只清有效範圍

擴展：多重心處理

樹可能有 1 或 2 個重心 (相鄰)。若需輸出所有重心：

// dfs2 中
if (mx < best_val) { best_val = mx; centroids.clear(); centroids.push_back(u); }
else if (mx == best_val) { centroids.push_back(u); }

總結

「樹的重心」是樹形 DP 經典入門模型：**換根 DP** 思想的最簡形式。第一遍自底向上聚合信息 (sz)，第二遍自頂向下分發補全信息 (N-sz[u])，雙遍掃描即得全局最優。掌握此模板，可解決「樹的重心」、「樹的直徑」、「到所有點距離和」等一大類問題。