Submission #640574

#	Time	Username	Problem	Language	Result	Execution time	Memory
640574		minhnhatnoe	Paprike (COI18_paprike)	C++17	100 / 100	52 ms	17544 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int cnt = 0;
vector<vector<int>> g;
vector<ll> h;
ll k;
ll dfs(int v, int p){
    vector<ll> sum;
    for (int u: g[v]){
        if (u == p) continue;
        sum.push_back(dfs(u, v));
    }
    ll sm = accumulate(sum.begin(), sum.end(), 0LL) + h[v];
    sort(sum.begin(), sum.end());
    while (sm > k){
        cnt++;
        sm -= sum.back();
        sum.pop_back();
    }
    return sm;
}


signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n >> k;
    g.resize(n);
    h.resize(n);
    for (int i=0; i<n; i++){
        cin >> h[i];
    }
    for (int i=1; i<n; i++){
        int a, b; cin >> a >> b;
        g[a-1].push_back(b-1);
        g[b-1].push_back(a-1);
    }
    dfs(0, -1);
    cout << cnt << '\n';
}

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