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

題目大意

給定一棵 N 節點樹（N ≤ 100,000），每個節點有權值（學生數）。刪除一條邊將樹分為兩部分，使兩部分權值和之差的絕對值最小。輸出最小差值。

解法：樹形 DP 計算子樹權值和

任選一個節點為根（如 1），DFS 計算每個節點為根的子樹權值和 dp[u]。總權值和為 sum。刪除邊 (u, parent[u]) 後，兩部分權值分別為 dp[u] 和 sum - dp[u]，差值為 |dp[u] - (sum - dp[u])| = |2*dp[u] - sum|。枚舉所有非根節點 u，取最小值。

代碼實現（C++）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
long long w[MAXN], dp[MAXN];
vector G[MAXN];
long long sum, ans;
int n;

void dfs(int u, int fa) {
    dp[u] = w[u];
    for (int v : G[u]) if (v != fa) {
        dfs(v, u);
        dp[u] += dp[v];
    }
}

int main() {
    int m, cas = 0;
    while (cin >> n >> m, n || m) {
        for (int i = 1; i <= n; ++i) {
            cin >> w[i]; sum += w[i];
            G[i].clear();
        }
        for (int i = 0; i < m; ++i) {
            int u, v; cin >> u >> v;
            G[u].push_back(v); G[v].push_back(u);
        }
        dfs(1, 0);
        ans = LLONG_MAX;
        for (int i = 2; i <= n; ++i)
            ans = min(ans, llabs(2*dp[i] - sum));
        cout << "Case " << ++cas << ": " << ans << '\n';
        sum = 0;
    }
    return 0;
}

複雜度

DFS O(N)，枚舉 O(N)，總 O(N)。遞歸深度可能達 100,000，需增加棧大小或用迭代 DFS。