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）。
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 }
原文：http://www.cnblogs.com/zyb993963526/p/6371832.html