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
vectorsons[maxn];
int n,T;
int dp(int u){
	if(sons[u].empty())return 1;
	int k=sons[u].size();
	vectord;
	for(int i=0;i