UVA 12186 Another Crisis：樹形 DP 計算最少請願工人數

題目描述

樹形層級結構，根為老闆（0），葉子為工人。非葉節點若其直接下屬中 ≥ T% 簽名，則會簽名並上交。求使老闆收到請願書所需最少工人數。

解題思路：自底向上樹形 DP

• dp[u] 表示使節點 u 簽名所需最少葉子工人數。
• 葉子節點（工人）：dp[u] = 1（自己簽名）。
• 內部節點：假設有 k 個子節點，需至少 need = ceil(k * T / 100) 個子節點簽名。收集所有子節點的 dp[v]，排序，取最小的 need 個求和。

C++ 代碼實現

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector children[MAXN];
int n, T;

int dfs(int u) {
    if (children[u].empty()) return 1; // 工人
    vector costs;
    for (int v : children[u]) costs.push_back(dfs(v));
    sort(costs.begin(), costs.end());
    int k = costs.size();
    int need = (k * T - 1) / 100 + 1; // ceil(k*T/100)
    int sum = 0;
    for (int i = 0; i < need; ++i) sum += costs[i];
    return sum;
}

int main() {
    while (scanf("%d%d", &n, &T) == 2) {
        for (int i = 0; i <= n; ++i) children[i].clear();
        for (int i = 1; i <= n; ++i) {
            int p; scanf("%d", &p);
            children[p].push_back(i);
        }
        printf("%d\n", dfs(0));
    }
    return 0;
}

複雜度

• 時間：O(n log n)（每節點排序子節點成本）。
• 空間：O(n)。