Submission #1309988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309988		wangzhiyi33	Paprike (COI18_paprike)	C++20	100 / 100	34 ms	17512 KiB

paprike

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

const int maxn=1e5;
int h[maxn+2],n,k;
vector<int>adj[maxn+2];
int ans=0;

int dfs(int cur,int par){
    vector<int>isi;
    int sum=h[cur];

    for(auto x : adj[cur]){
        if(x==par)continue;
        isi.push_back(dfs(x,cur));
        sum+=isi.back();
    }
    sort(isi.begin(),isi.end());

    for(int q=isi.size()-1;q>=0 && sum>k;q--){
        ans++;
        sum-=isi[q];
    }
    return sum;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int q=1;q<=n;q++)cin>>h[q];
    for(int q=1;q<n;q++){
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,-1);
    cout<<ans<<endl;
}

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