1.题目描述：点击打开链接
2.解题思路：本题利用树状dp解决，不过其实也可以理解为用贪心法解决的。设d(u)表示u给上级发信最少需要的工人个数，假设u有k个子结点，那么根据题意，至少需要c=(k*T-1)/100+1个直属下属发信才行。而每个直属下属的工人数是di，那么这时只需要把di由小到大排序，然后把前c个相加就是d(u)了。最终的答案是d(0)。由于需要排序，因此总的时间复杂度是O(N*logN)。最后附上一篇带有大量宏定义的参考代码，真心给跪，第一次见这么多的宏定义，Orz。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;const int maxn = 1e5 + 10;vector<int>sons[maxn];//存放i的所有直属下属int n, T;int dp(int u){if (sons[u].empty())return 1;//工人int k = sons[u].size();vector<int>d; //存放u的直属下属的工人数for (int i = 0; i < k; i++)d.push_back(dp(sons[u][i]));sort(d.begin(), d.end());int c = (k*T – 1) / 100 + 1;int ans = 0;for (int i = 0; i < c; i++)ans += d[i];return ans;}int main(){//freopen("test.txt", "r", stdin);while (scanf("%d%d", &n, &T) == 2 && n&&T){memset(sons, 0, sizeof(sons));int x;for (int i = 1; i <= n; i++){scanf("%d", &x);sons[x].push_back(i);}int ans;ans = dp(0);printf("%d\n", ans);}return 0;}
参考代码：
#include <cstdio>#include <iostream>#include <cstring>#include <string>#include <algorithm>#include <map>#include <set>#include <list>#include <stack>#include <vector>#include <queue>#include <cmath>#include <cstdlib>using namespace std;#define PBpush_back#define SIZE(x)(int)x.size()#define clr(x,y)memset(x,y,sizeof(x))#define RS(n)scanf ("%s", n)#define RD(n)scanf ("%d", &n)#define RF(n)scanf ("%lf", &n)#define ALL(t)(t).begin(),(t).end()#define FOR(i,n,m,step) for (int i = n; i <= m; i += step)#define ROF(i,n,m,step) for (int i = n; i >= m; i -= step)#define ITiteratortypedef long longll;typedef unsigned intuint;typedef unsigned long longull;typedef vector<int>vint;typedef vector<long long>vll;typedef vector<string>vstring;typedef pair<int, int>PII;/*****************************************************************/const int maxn = 100000 + 5;vint sons[maxn];int T;int dp(int u) {if (sons[u].empty()) return 1;int k = sons[u].size();vint d;FOR(i,0,k-1,1) d.PB(dp(sons[u][i]));sort(d.begin(),d.end());int c = (k * T – 1) / 100 + 1;int ans = 0;FOR(i,0,c – 1,1) ans += d[i];return ans;}int main() {int n;while (cin>>n>>T,n) {FOR(i,0,n,1) sons[i].clear();FOR(i,1,n,1) {int tmp;RD(tmp);sons[tmp].PB(i);}cout<<dp(0)<<endl;}}
，把你的脸迎向阳光，那就不会有阴影
