Submission #1124271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124271		njoop	Paprike (COI18_paprike)	C++17	100 / 100	88 ms	17632 KiB

paprike

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

int n, k, h[100010], x, y, ans;

vector<int> g[100010];

int dfs(int no, int pa) {
    int sum = h[no];
    vector<int> v;
    for(int i: g[no]) {
        if(i == pa) continue;
        v.push_back(dfs(i, no));
        sum += v.back();
    }
    sort(v.begin(), v.end());
    while(sum > k) {
        sum -= v.back();
        v.pop_back();
        ans++;
    }
    return sum;
}

signed main() {
    cin >> n >> k;
    for(int i=1; i<=n; i++) {
        cin >> h[i];
    }
    for(int i=1; i<n; i++) {
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, -1);
    cout << ans;
    return 0;
}

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