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

https://vjudge.net/problem/UVA-12186

题意：

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

思路：

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

 #include<iostream>

 #include<vector>

 #include<algorithm>

 using namespace std;

 const int maxn =  + ;

 int n, t;

 vector<int> sons[maxn];

 int dp(int u)

 {

     if (sons[u].empty())  return ;

     vector<int> d;

     int k = sons[u].size();

     for (int i = ; i < k; i++)

         d.push_back(dp(sons[u][i]));

     sort(d.begin(), d.end());

     int c = (k*t - ) /  + ;

     int ans = ;

     for (int i = ; i < c; i++)

         ans += d[i];

     return ans;

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     int temp;

     while (cin >> n >> t && (n || t))

     {

         for (int i = ; i <= n; i++)

             sons[i].clear();

         for (int i = ; i <= n; i++)

         {

             cin >> temp;

             sons[temp].push_back(i);

         }

         int ans=dp();

         cout << ans << endl;

     }

     return ;

 }