제출 #850948

#제출 시각아이디문제언어결과실행 시간메모리
850948CyanmondPaprike (COI18_paprike)C++17
100 / 100
39 ms21072 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, l, r) for (int i = (l); i < (r); ++i) #define per(i, l, r) for (int i = (r - 1); i >= l; --i) #define ALL(x) (x).begin(), (x).end() using i64 = long long; void main_() { int N; i64 K; cin >> N >> K; vector<i64> H(N); for (auto &e : H) cin >> e; vector<vector<int>> Tree(N); rep(i, 0, N - 1) { int a, b; cin >> a >> b; --a, --b; Tree[a].push_back(b); Tree[b].push_back(a); } int ans = 0; auto dfs = [&](auto &&self, const int v, const int p) -> i64 { vector<i64> res; for (const auto t : Tree[v]) { if (t == p) continue; res.push_back(self(self, t, v)); } sort(ALL(res)); bool isOk = true; i64 s = 0; for (const auto e : res) { if (isOk and s + e + H[v] <= K) { s += e; } else { isOk = false; ++ans; } } return s + H[v]; }; dfs(dfs, 0, -1); cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); main_(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...