UVa 12186 工人的请愿书（树形DP）

题意：

一个老板和n个员工组成树状结构，每个员工都有自己的唯一上司，老板的编号为0，员工1~n，工人们打算签署一个志愿书给老板，但无法跨级，当一个中级员工（非是工人的员工）的直属下属中不小于T%的人签字时，他也会签字并且递给他的直属上司，问：要让老板收到请愿书至少需要多少个工人签字

思路：

设d（u）表示让u给上级发信最少需要多少个工人。假设u有k个子节点，则至少需要c=（k*T-1）/100+1个直接下属发信才行。把所有子节点的d值从小到大排序，前c个加起来即可。最终答案是d（0）。

 1 #include<iostream> 
 2 #include<vector>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 100000 + 5;
 7 
 8 int n, t;
 9 vector<int> sons[maxn];
10 
11 
12 int dp(int u)
13 {
14     if (sons[u].empty())  return 1;
15     vector<int> d;
16     int k = sons[u].size();
17     for (int i = 0; i < k; i++)
18         d.push_back(dp(sons[u][i]));
19     sort(d.begin(), d.end());
20     int c = (k*t - 1) / 100 + 1;
21     int ans = 0;
22     for (int i = 0; i < c; i++)
23         ans += d[i];
24     return ans;
25 }
26 
27 int main()
28 {
29     //freopen("D:\txt.txt", "r", stdin);
30     int temp;
31     while (cin >> n >> t && (n || t))
32     {
33         for (int i = 0; i <= n; i++)
34             sons[i].clear();
35         for (int i = 1; i <= n; i++)
36         {
37             cin >> temp;
38             sons[temp].push_back(i);
39         }
40         int ans=dp(0);
41         cout << ans << endl;
42     }
43     return 0;
44 }