Submission #640573

#	Time	Username	Problem	Language	Result	Execution time	Memory
640573		hotboy2703	Paprike (COI18_paprike)	C++14	100 / 100	70 ms	19208 KiB

paprike

#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long h[100100];
vector <long long> g[100100];
pair <long long,long long> dp[100100];
void dfs(long long u,long long pre){
    for (auto v:g[u]){
        if (v == pre)continue;
        dfs(v,u);
    }
    dp[u] = {0,h[u]};
    vector <long long> all;
    for (auto v:g[u]){
        if (v == pre)continue;
        dp[u].first += dp[v].first;
        dp[u].second += dp[v].second;
        all.push_back(dp[v].second);
    }
    sort(all.begin(),all.end(),greater <long long> ());
    long long cur = 0;
    while (dp[u].second > k){
        dp[u].second -= all[cur];
        cur++;
        dp[u].first++;
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>k;
    for (long long i = 1;i <= n;i ++){
        cin>>h[i];
    }
    for (long long i = 1;i < n;i ++){
        long long x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,1);
    cout<<dp[1].first<<'\n';
    return 0;
}

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