dp uva12186树上的动态规划

d(u)表示让u给上级发信最少需要多少工人
 1 #include <bits/stdc++.h>  
 2 using namespace std;  
 3   
 4 const int maxn = 1e5+10;  
 5 int N,T,f;  
 6 vector<int> sons[maxn];  
 7   
 8 int dp(int u){  
 9     if(sons[u].empty()) return 1;  
10     int k = sons[u].size();  
11     vector<int> d;  
12     for(int i=0; i<k; i++)  
13         d.push_back(dp(sons[u][i]));  
14     sort(d.begin(),d.end());  
15     int c = (k*T-1)/100 + 1;  
16     int ans = 0;  
17     for(int i=0; i<c; i++) ans += d[i];  
18   
19     return ans;  
20 }  
21   
22 int main(){  
23     while(scanf("%d%d",&N,&T)==2 && (N||T)){  
24         for(int i=0; i<=N; i++) sons[i].clear();  
25         for(int i=1; i<=N; i++){  
26             scanf("%d",&f);  
27             sons[f].push_back(i);  
28         }  
29         printf("%d
",dp(0));  
30     }  
31   
32 }  
33