POJ 3140 Contestants Division：樹形 DP 求最小分割差值

問題大意

給定一棵 n 節點的樹（n ≤ 100,000），每個節點有學生數。刪除一條邊將樹分成兩部分，使兩部分學生總數差值最小。輸出最小差值。

樹形 DP 思路

• 任選根節點（如 1），DFS 計算每個節點為根的子樹學生總和 dp[u]。
• 刪除邊 (u, parent) 後，兩部分學生數分別為 dp[u] 和 total - dp[u]。
• 差值為 |total - 2*dp[u]|。遍歷所有節點取最小值。

關鍵實現細節

用鏈式前向星存圖，避免遞歸棧溢出可用非遞歸 DFS。注意長長整型防止溢出（學生數 ≤ 1e8，n ≤ 1e5，總和 ≤ 1e13）。

代碼片段

void dfs(int u, int fa) {
    dp[u] = num[u];
    for (auto e = head[u]; e; e = e->next) {
        int v = e->v;
        if (v == fa) continue;
        dfs(v, u);
        dp[u] += dp[v];
    }
}

void solve() {
    dfs(1, 0);
    long long ans = INF;
    for (int i = 1; i <= n; ++i)
        ans = min(ans, llabs(total - 2*dp[i]));
    cout << ans << endl;
}

心得

題目本質是樹上任意邊分割，子樹和預處理後 O(n) 掃描即可。注意初始化與邊界條件，曾因 INF 定義不當導致多次 WA。