Another Crisis UVA

一道很水的题

树形dp

题目连接 https://vjudge.net/problem/UVA-12186

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+10;

vector<int> son[maxn];

int n,t;

int dfs(int u) {
    if(son[u].empty()) return 1;
    int k=son[u].size();
    vector<int> d;
    for(int i=0;i<k;i++)
    d.push_back(dfs(son[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() {
    while(scanf("%d%d",&n,&t)) {
        for(int i=0;i<=n;i++) son[i].clear();
        if(n==0&&t==0) break;
        for(int i=1;i<=n;i++) {
            int fa;scanf("%d",&fa);
            son[fa].push_back(i);
        }
        printf("%d
",dfs(0));
    }
    return 0;
}