Submission #609170

#	Time	Username	Problem	Language	Result	Execution time	Memory
609170		sword060	Paprike (COI18_paprike)	C++17	100 / 100	67 ms	19096 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
int x,k,ans,a[100005];
vector<int>v[100005];
int dfs(int i,int p=-1){
  vector<int>lol;
  for(auto j:v[i]){
    if(j==p)continue;
    lol.push_back(dfs(j,i));
  }
  int ret=a[i];
  sort(lol.begin(),lol.end());
  for(auto j:lol)if(ret+j<=k)ret+=j;else ans++;
  return ret;
}
int main(){
  ios::sync_with_stdio(0); cin.tie(0);
  cin>>x>>k;
  for(int i=1;i<=x;i++)cin>>a[i];
  for(int i=1;i<=x-1;i++){
    int l,r;cin>>l>>r;
    v[l].push_back(r);
    v[r].push_back(l);
  }
  dfs(1);
  cout<<ans;
	return 0;
}

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