HDU 3452：Bonsai（盆栽修剪——樹形 DP 與最小割）

問題：給定一棵帶權無向樹，根節點為 r。需移除一些邊，使原樹中所有葉子節點均與根斷開。求移除邊的最小總權重。

方法一：樹形 DP

定義 dp[u] 為切斷以 u 為根的子樹中所有葉子到 u 的連接所需最小代價。遞推：

• 若 u 是葉子，dp[u] = 0（無需切斷自身）。
• 否則對每個子節點 v，可選擇切斷邊 (u,v) 代價 w，或保留邊並承擔 dp[v]。取較小值累加：dp[u] += min(dp[v], w)。

方法二：最小割 / 最大流

建立流網絡：源點 S 連向根 r（容量 INF），每個葉子連向匯點 T（容量 INF），樹邊雙向連接（容量為邊權）。根據最大流最小割定理，最小割即為答案。

代碼片段（樹形 DP）

void dfs(int u, int fa) {
    int sum = 0;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v == fa) continue;
        dfs(v, u);
        sum += min(dp[v], edge[i].val);
    }
    if (sum) dp[u] = sum;
}

兩種方法各有優劣：樹形 DP 代碼簡潔、時空效率高；最小割模型通用性強，適合更複雜的約束條件。