题解UVa12186 工人的请愿书

刘汝佳大法好！

设$dp(u)$表示让$u$号员工给上级发信至少需要多少个工人。

那么假设$u$的子节点个数为$k$个，则至少需要$c=(kT-1)/100+1$个直接下属发信才可以让$u$号员工给上级发信（注意以上公式括号内的$-1$是为了防止$kT$为$100$的倍数而减一的）。

则我们更新$dp(u)$的方法是：将$u$的$k$个下属中$dp$值最小的$c$个做和，即可保证$dp(u)$是最小的。

最后答案就是$dp(0)$。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=1e5+5;
int n,t;
int target[N],pre[N],last[N],tot=0;
void add(int u,int v) {
    target[++tot] = v;
    pre[tot] = last[u];
    last[u] =  tot;
}
int dfs(int u) {
    if(!last[u]) return 1;
    int tmp[N],cnt=0;
    for(int ptr=last[u];ptr;ptr=pre[ptr]) {
        tmp[++cnt]=dfs(target[ptr]);
    }
    sort(tmp+1,tmp+cnt+1);
    int ned = (cnt*t-1)/100+1,dp=0;
    rep(i,1,ned) dp+=tmp[i]; //取最小的c个dp值
    return dp;
}
int main(){
    while(~scanf("%d%d",&n,&t)&&n&&t) {
        tot=0;
        memset(last,0,sizeof(last));
        rep(i,1,n) {
            int x;
            scanf("%d",&x);
            add(x+1,i+1); //这里我把点的编号加一了，从0~n变成了1~n+1
        }
        printf("%d\n",dfs(1));
    }
    return 0;
}