HDU 3586 Information Disturbing：二分答案 + 樹形 DP

題目大意

給定一棵 N 節點樹（N ≤ 1000），根為 1，葉子節點為前線士兵。需切斷若干邊，使所有葉子與根斷開。切斷邊的代價為 w，要求：(1) 被切斷邊的權值之和 ≤ M；(2) 每條被切斷邊的權值 ≤ X（裝置上限功率）。求最小的 X。若無解輸出 -1。

解題思路：二分 + 判斷可行性

X 的範圍 [1, 1000]（邊權上限）。二分 X，判斷在「只能切斷權值 ≤ X 的邊」且「總代價 ≤ M」下，能否切斷所有葉子到根的路徑。

樹形 DP 判斷

定義 dfs(u, fa, X) 返回以 u 為根的子樹中，為切斷所有葉子到 u 的路徑所需的最小代價。若 u 是葉子（除根外度為 1），必須切斷其到父節點的邊，若該邊權 > X 則返回 INF（不可行），否則返回該邊權。對於內部節點，對每個子樹 v，遞歸得到 cost_v = dfs(v, u, X)。若 cost_v > w(u,v) 且 w(u,v) ≤ X，則選擇切斷 (u,v) 邊，代價為 w(u,v)；否則累加 cost_v。最終根節點的返回值即為最小總代價，判斷是否 ≤ M。

代碼關鍵部分

const int INF = 1e9;
int dfs(int u, int fa, int limit) {
    int sum = 0, is_leaf = 1;
    for (auto [v, w] : G[u]) if (v != fa) {
        is_leaf = 0;
        int child_cost = dfs(v, u, limit);
        if (child_cost > w && w <= limit) child_cost = w; // 切斷當前邊更划算
        sum += child_cost;
    }
    if (is_leaf) return INF; // 葉子必須由父節點切斷
    return sum;
}

bool check(int X) {
    return dfs(1, 0, X) <= M;
}

// 二分主循環
int l = 1, r = 1000, ans = -1;
while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid)) { ans = mid; r = mid - 1; }
    else l = mid + 1;
}

注意事項

• INF 不能太大，防止加法溢出（如 1e9 足夠）。
• 根節點若為葉子（N=1）需特判，但題目 N>1。
• 遞歸深度可能達 1000，需增棧或用迭代。