题意：给出一个树状关系图，公司里只有一个老板编号为0，其他人员从1开始编号。除了老板，每个人都有一个直接上司，没有下属的员工成为工人。工人们想写一份加工资的请愿书，只有当不少于员工的所有下属的T%人递交请愿书后，该员工才会将请愿书递交给他的直接上级。输出能递交到老板处，最少需要多少工人写请愿书思路：
d(u)表示让u给上级发信最少需要多少个工人。假设u有k个子节点，则至少需要c = (k*T – 1) / 100 + 1 个直接下级发信给他才行。把所有子节点的d从小到大排序，前c个和就是d(u)。而所求答案就是d(0)。
从枝叶向树根dp即可，不过搜索的形式dp会更简单，就不需要再dfs预处理了
//AcceptedC++0.245#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<vector>using namespace std;const int N=1e5+1e2;int T;int n;int mdep;int dp[N]; //此人给上级发信最少需要多少个最底层工人vector<int> dep[N];struct Edge{int v;Edge(int _v=0) : v(_v) {};};vector <Edge> es[N];//每个节点的儿子void dfs_makedep(int u,int d) //统计每个深度有哪些结点，，从枝叶向根递推{mdep=max(mdep,d);dep[d].push_back(u);for(int i=0;i<es[u].size();i++){dfs_makedep(es[u][i].v,d+1);}}void ini(){mdep=-1;memset(dp,0,sizeof(dp));for(int i=0;i<=n;i++){es[i].clear();dep[i].clear();}}int main(){while(scanf("%d%d",&n,&T),(T||n)){ini();for(int v=1;v<=n;v++){int u;scanf("%d",&u);es[u].push_back(Edge(v));}dfs_makedep(0,0);for(int l=mdep;l>=0;l–)for(int i=0;i<dep[l].size();i++){int u=dep[l][i];if(es[u].empty()) //border{dp[u]=1;continue;}vector<int>tmp;for(int j=0;j<es[u].size();j++)tmp.push_back(dp[es[u][j].v]);sort(tmp.begin(),tmp.end());int c=(es[u].size()*T-1)/100 + 1;//小技巧for(int k=0;k<c;k++)dp[u]+=tmp[k];}printf("%d\n",dp[0]);}return 0;}
而消极的人则在每个机会都看到某种忧患。
