제출 #1293973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293973		ayaz	Paprike (COI18_paprike)	C++20	100 / 100	48 ms	22312 KiB

paprike

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
#define ll long long
#define int ll
#define ui unsigned int
#define pb push_back
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())
#define vi vector<int> 
#define ost tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int sz = 1e6, inf = 1e9;
const ll mod = 998244353, INF = 1e18;

vi g[sz];
int a[sz], ans = 0, n, k;
int dfs(int u, int p){
  int sm = a[u];
  multiset<int> edges;
  for (auto &v : g[u]) {
    if (v == p) continue;
    edges.insert(dfs(v, u));
  }
  int cnt = 0;
  for (auto &i : edges) {
    if (sm + i > k) break;
    sm += i;
    cnt++;
  }
  ans += (isz(edges) - cnt);
  return sm;
}
void solve(int tc) {
  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].pb(v);
    g[v].pb(u);
  }
  dfs(1, -1);
  cout << ans << "\n";
}
void precompute() {}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef LOCAL
  freopen("in.txt", "r", stdin);
  freopen("err.log", "w", stderr);
#endif
  precompute();
  int t = 1;
  // cin >> t;
  for (int tc = 1; tc <= t; tc++) solve(tc);
  return 0;    
}

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