树型DP第一题。。。就是从boss到底层员工是一个树型结构，底层员工想加薪，如果每个boss都有超过T%的员工要求加薪，他就会往更高的bOSs传达，问如果让根节点的大boss接到加薪要求，最少要有多少名员工提出加薪要求。d[u]表示u如果提出加薪，所需要的员工数，很明显，最底层的员工肯定都要求加薪，对每一个非叶子节点u，只要子节点的T%要加薪即可，那么为使总员工数最少，把u的子节点的d【】值从小到大排序，只需要找子节点数目的T%的员工就可以了，所以用到一个优先队列。DP过程用记忆化搜索来实现。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
#include<queue>
#define INF 1e6
using namespace std;
const int maxn = 1e5+; int n,T;
vector<int> g[maxn];
int ch[maxn];
int dp(int u)
{
if(g[u].size() == ) return ;
priority_queue<int,vector<int>,greater<int> > que;
for(int i = ; i < g[u].size(); ++i)
{
int to = g[u][i];
que.push(dp(to));
}
int sum = ;
//printf("%d ",ch[u]);
for(int i = ; i < ch[u]; ++i)
{
sum+=que.top();
que.pop();
}
return sum;
}
int main()
{
//freopen("in","r",stdin);
while(~scanf("%d%d",&n,&T))
{
if(n == &&T ==) break;
int fa;
for(int i = ; i <= n; ++i)
{
scanf("%d",&fa);
g[fa].push_back(i);
}
for(int i = ; i <= n; ++i)//if(T == 100) ch[i] = g[i].size();
ch[i] = (int)(ceil(1.0*g[i].size()*T/));
cout<<dp();
printf("\n");
for(int i = ; i <= n; ++i) g[i].clear();
}
}