제출 #1107357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1107357		0pt1mus23	Paprike (COI18_paprike)	C++14	13 / 100	49 ms	21232 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 1e5 +5, inf = INT_MAX, LL = 30;
int k ;
pair<int,int> dp[sze];
int val[sze];
vector<int> graph[sze];

void dfs(int node,int par=-1){
    
    for(auto v:graph[node]){
        if(v!=par){
            dfs(v,node);
        }
    }
    vector<int> lst;
    int sum=val[node];
    for(auto v:graph[node]){
        if(v!=par){
            dp[node].first += dp[v].first;
            lst.pb(dp[v].second);
            sum+=dp[v].second;
        }
    }
    sort(all(lst));
    while(sum>k){
        sum-=lst.back();
        dp[node].first ++;
    }
    dp[node].second = sum;
}


void rush(){
    int n;
    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;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    dfs(1);
    putr(dp[1].first);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tt = 1; 
    // cin>>tt;

    while(tt--){
        rush();
    }

    return 0;
}

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