Submission #1293886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293886		littleprofessor	Paprike (COI18_paprike)	C++20	100 / 100	37 ms	17164 KiB

paprike

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

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

vector<int> v[100001];
int h[100001];
long long k;
long long cuts = 0;

long long dfs(int u, int p) {
    vector<long long> sums;

    for (int x : v[u]) {
        if (x == p) continue;
        long long s = dfs(x, u);
        if (s > k) {
            cuts++;
        } else {
            sums.push_back(s);
        }
    }

    sort(sums.begin(), sums.end());
    long long sum = h[u];

    for (long long i : sums) {
        if (sum + i <= k) {
            sum += i;
        } 
        else {
            cuts++;
        }
    }
    return sum;
}

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n>>k;

    for(int i = 1 ; i <= n ; i++) cin>>h[i];
    for(int i = 0 ; i < n-1 ; i++) {
        int x, y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1,-1);

    cout<<cuts<<endl;
    return 0;
}

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