제출 #1124269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124269		njoop	Paprike (COI18_paprike)	C++17	24 / 100	86 ms	17224 KiB

paprike

#include <bits/stdc++.h>

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;
}

int 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: 0 / 27
• Subtask 4: 0 / 49