UVA-12186 Another Crisis （树状DP）
题目大意：一家工厂，一个老板（编号为0），n个工人（编号1~n），其中，有的工人是中层领导，管辖一部分其他工人。现在大家要签署一份加薪申请书，但是按照规定不能越级*，所以只能通过一层层的中间领导传到老板手中。当某个中间领导的手下签名员工人数达到 m% 时，他也会签上自己的名字。为确保申请书顺利到达老板手中，至少需要多少名员工签名。
题目分析：定义d(i)表示员工 i 将申请书传给上一级所需的最少签名人数。设k为i的“儿子”数目，则最少需要的签名人数为 c=(k*m-1)/100+1。所以dp(i)=sum(dp(j))。（其中，j是i的儿子，并且dp(j)是前c个最小的。
代码如下：
# include<iostream>
# include<cstdio>
# include<vector>
# include<cstring>
# include<algorithm>
using namespace std;
int n,m;
vector<int>sons[100005];
int DP(int u)
{
if(sons[u].empty())
return 1;
vector<int>d;
int k=sons[u].size();
for(int i=0;i<k;++i)
d.push_back(DP(sons[u][i]));
sort(d.begin(),d.end());
int c=(k*m-1)/100+1;
int ans=0;
for(int i=0;i<c;++i)
ans+=d[i];
return ans;
}
int main()
{
int a;
while(scanf("%d%d",&n,&m)&&n+m)
{
for(int i=0;i<=n;++i)
sons[i].clear();
for(int i=1;i<=n;++i){
scanf("%d",&a);
sons[a].push_back(i);
}
printf("%d
",DP(0));
}
return 0;
}