UVA 12186 Another Crisis

?

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

算法分析：设d[u]表示让u给上级发信至少需要多少个工人。假设u有k个子节点，则至少需要C=(kT-1)100+1的直接下属发信才行。把所有的子节点的d值从小到大排序，前C个加起来即可。时间复杂度：O(nlogn)

代码：

?

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; #define maxn 100005 vector
      
       sons[maxn]; int n,T; int dp(int u){ if(sons[u].empty())return 1; int k=sons[u].size(); vector
       
        d; for(int i=0;i
        
         
?