Submission #1043903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043903		vjudge1	Paprike (COI18_paprike)	C++17	100 / 100	63 ms	15988 KiB

paprike

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100'000 + 10;
int n, k, par[N], c[N];
ll a[N];
vector<int> G[N];
int ans = 0;

void dfs(int v, int p = 0)
{
  vector<ll> vec;
  for(int u : G[v])
    if(u != p)
      dfs(u, v), vec.push_back(a[u]);
  sort(vec.begin(), vec.end());

  for(ll i : vec)
    if(i + a[v] <= k)
      a[v] += i;
    else
      ans++;
}

int main()
{
  cin >> n >> k;
  for(int i = 1; i <= n; i++)
    cin >> a[i];
  
  for(int i = 1; i < n; i ++)
    {
      int u, v;
      cin >> u >> v;
      G[u].push_back(v);
      G[v].push_back(u);
    }
  dfs(1);
  cout << ans << endl;
  return 0;
}

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