Submission #1118285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118285		vjudge1	Paprike (COI18_paprike)	C++17	100 / 100	117 ms	25896 KiB

paprike

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

const int ssz = 2e5 + 5;
vector<int> adj[ssz], a(ssz);
array<int,2> dp[ssz];
int n, k;

void dfs(int node,int par = -1){
    dp[node] = {a[node], 0};
    vector<int>val;
    for(auto i : adj[node]){
        if(i == par){
            continue;
        }
        dfs(i, node);
        val.push_back(dp[i][0]);
        dp[node][1] += dp[i][1] + 1;
    }
    sort(val.begin(), val.end());
    reverse(val.begin(), val.end());
    while(!val.empty() && dp[node][0] + val.back() <= k){
        dp[node][0] += val.back();
        dp[node][1]--;
        val.pop_back();
    }
}

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    for(int i = 0; i < n - 1; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    cout << dp[1][1] << endl;
}

signed main(){
    int T = 1;
    while(T--){
        solve();
    }
}

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