0%

UVA12186 工人的请愿书

题目链接

设$f[u]$为节点$u$收到信所需要的工人数。

假设节点$u$有$k$个直接下属,根据题目条件,就需要$less=(k*T-1)/100+1$个工人签字(这样写其实是为了向上取整)。

那么状态转移就是把子节点按$f[j]$从小到大排序之后,把前$less$个节点的$f[j]$加起来就行了。

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

const int maxn=1e5+7;
int n,T,f[maxn];
vector<int> q[maxn];

void dfs(int u,int fa) {
    if(q[u].empty()) {f[u]=1;return;}
    int k=q[u].size();
    for(int i=0;i<k;i++) {
        int v=q[u][i];
        if(v==fa) continue;
        dfs(v,u);
    }
    int less=(k*T-1)/100+1;
    vector<int> d;
    for(int i=0;i<k;i++) d.push_back(f[q[u][i]]);
    sort(d.begin(),d.end());
    for(int i=0;i<less;i++) f[u]+=d[i];
}

int main() {
    while(cin>>n>>T&&n){
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++) {
            int a;
            cin>>a;
            q[a].push_back(i);
        }
        dfs(0,0);
        cout<<f[0]<<endl;
        for(int i=0;i<n;i++) q[i].clear();
    }
        return 0;
}