Submission #1118302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118302		vjudge1	Paprike (COI18_paprike)	C++17	100 / 100	95 ms	17596 KiB

paprike

#include "bits/stdc++.h"

using ll = long long;
using namespace std;

const int mxN = 100005;

vector<int> aj[mxN];
ll a[mxN];
int cnt;
ll K;

ll dfs(int u, int p = 0) {
    vector<ll> r;
    ll sm = a[u];
    for (int v : aj[u]) {
        if (v ^ p) {
            r.push_back(dfs(v, u));
        }
    }
    sort(begin(r),end(r));
    for (int i : r) {
        if (sm + i <= K) {
            sm += i;
        } else {
            cnt ++;
        }
    }
    return sm;
}

int main() {
    int N;
    cin >> N >> K;

    for (int i = 1; i <= N; i ++) {
        cin >> a[i];
    }

    for (int i = 1; i <= N - 1; i ++) {
        int X, Y;
        cin >> X >> Y;
        aj[X].push_back(Y);
        aj[Y].push_back(X);
    }

    dfs(1, 0);
    cout << cnt << endl;
}

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