Uva 12186 工人的请愿书

题目链接：https://uva.onlinejudge.org/external/121/12186.pdf

题意：

给出一个树状关系图，公司里只有一个老板编号为0，其他人员从1开始编号。除了老板，每个人都有一个直接上司，没有下属的员工成为工人。

工人们想写一份加工资的请愿书，只有当不少于员工的所有下属的T%人递交请愿书后，该员工才会将请愿书递交给他的直接上级。输出能递交到老板处，最少需要多少工人写请愿书。

分析：

d(u) 表示让 u 放给上级的最优解， u 有 k 个子节点，那么至少需要 c = (k*T-1)/100 + 1个下属; （这里的数学公式很重要，刚开始我写的 k*T/100，是不对的，因为，如果k*T/100 = 5.5,那么需要6个下属，但是计算结果却是5，用(k*T-1)/100 + 1 则是5.49 + 1 = 6了，如果刚好整除，就是4.99 + 1 = 5了，符合至少 %T的要求） 然后状态转移就是最小的那 c 个下属。

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

#define maxn 100000

int n,T;
vector <int> sons[maxn];

int dp(int u) {
    if(sons[u].size()==0) return 1;

    int k = sons[u].size();

    vector<int> d;
    d.clear();

    for(int i=0;i<k;i++) {
        int v = sons[u][i];
        d.push_back(dp(v));
    }

    sort(d.begin(),d.end());

    int ans = 0;
    int c = (k*T-1)/100+1;
    for(int i=0;i<c;i++) {
        ans+=d[i];
    }

    return ans;

}

int main()
{
    while(scanf("%d%d",&n,&T),n) {

        for(int i=0;i<=n;i++)
            sons[i].clear();

        for(int i=1;i<=n;i++) {
            int u;
            scanf("%d",&u);
            sons[u].push_back(i);
        }

        int ans = dp(0);

        printf("%d
",ans);

    }


    return 0;
}