题目链接:https://vjudge.net/contest/307650#problem/A
题目大意:

思路:

设d(u)表示让u给上级发信最少需要多少个工人。假设u有k个子结点,则至少需要c=kT/100+(kT%100==0?0:1)个直接下属发信才行。把所有子结点的d值从小到大排序,前c个加起来即可。最终 答案是d(0)。因为要排序,算法的时间复杂度为O(nlogn)。动态规划部分代码如下:

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

vector<int> e[100010];
int n, T, x, y;
int dp(int u)
{
    if(e[u].empty())
    {
        return 1;
    }
    vector<int> son;
    int k=e[u].size();
    int c=k*T/100+(k*T%100==0?0:1);//u的下级应该***的人数
    
    for(int i=0;i<k;i++)
    {
        son.push_back(dp(e[u][i]));
    }
    
    sort(son.begin(), son.end());
    int ans=0;
    for(int i=0;i<c;i++)//选择需要***人数最少的c个下级
    {
        ans+=son[i];
    }

    return ans;
}

int main()
{
    while(scanf("%d%d",&n,&T),n*T)
    {
        memset(e, 0, sizeof(e));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x,&y);
            e[x].push_back(i);
        }
        printf("%d\n",dp(0));
    }

    return 0;
}