（UVA - 12186）Another Crisis（树状dp）

太阳不下山

　　https://vjudge.net/problem/UVA-12186

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
#define pb push_back
#define rep(i,a,n) for(int i=a; i<n; i++)
typedef long long ll;
typedef unsigned long long ull;
const int mod=1e9+7;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
int n,T;
vector<int>son[N];
int tree_dp(int u)
{
  if(son[u].empty()) return 1;
  int k=son[u].size();
  vector<int>d;
  rep(i,0,k) d.pb(tree_dp(son[u][i]));
  sort(d.begin(),d.end());
  int c=(k*T-1)*0.01+1,ans=0;///c为最少的工人数
  rep(i,0,c) ans+=d[i];
  return ans;
}
int main()
{
  while(~scanf("%d%d",&n,&T)&&n&&T)
  {
    int x;
    rep(i,0,n+1) son[i].clear();
    rep(i,1,n+1) scanf("%d",&x),son[x].pb(i);///son[x]记录其直接下属
    printf("%d\n",tree_dp(0));
  }
  return 0;
}