제출 #1220082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220082		AlgorithmWarrior	Paprike (COI18_paprike)	C++20	100 / 100	66 ms	18004 KiB

paprike

#include <bits/stdc++.h>

using namespace std;

int const NMAX=100005;
int n,k;
int v[NMAX];
vector<int>tree[NMAX];

void read(){
    cin>>n>>k;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
    for(i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
}

int tai[NMAX];
int sum[NMAX];

void dfs(int nod,int tata){
    long long s=v[nod];
    vector<int>sms;
    for(auto fiu : tree[nod])
        if(fiu!=tata){
            dfs(fiu,nod);
            tai[nod]+=tai[fiu];
            s+=sum[fiu];
            sms.push_back(sum[fiu]);
        }
    sort(sms.begin(),sms.end());
    while(s>k){
        s-=sms.back();
        sms.pop_back();
        ++tai[nod];
    }
    sum[nod]=s;
}

int main()
{
    read();
    dfs(1,0);
    cout<<tai[1];
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49