Submission #1117927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117927		vjudge1	Paprike (COI18_paprike)	C++17	100 / 100	51 ms	19896 KiB

paprike

// author - alimammadzade

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

const int N = 1e5 + 1;
vector<int> g[N];
int n, k, res, sz[N], val[N];

void dfs(int u, int p) {
    vector<int> subt;
    sz[u] = val[u];
    for (int v : g[u]) if (v != p) {
        dfs(v, u);
        subt.push_back(sz[v]);
        sz[u] += sz[v];
    }
    sort(subt.rbegin(), subt.rend());
    for (int v : subt)
        if (sz[u] > k) sz[u] -= v, res++;
        else break;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    // system("cls"), freopen("in.txt", "r", stdin);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 1);
    cout << res;
}

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