#include <bits/stdc++.h>
using namespace std;
template<typename T1, typename T2>ostream& operator<<(ostream &os, const pair<T1, T2> &p) {return os << '{' << p.first << ", " << p.second << '}';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K, V>& m) {os << "{";for (auto it = m.begin(); it != m.end(); ++it) {if (it != m.begin()) os << ", "; os << it->first << " : " << it->second;}return os << "}";}
void debug() { cerr << endl; }
template<typename Head, typename... Tail>
void debug(Head H, Tail... T) { cerr << H; debug(T...); }
#ifdef ONPC
#define deb(...) cerr << '[' << __FILE__ << ':' << __LINE__ << "] (" << #__VA_ARGS__ << "):", debug(__VA_ARGS__)
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define deb(...)
#endif
const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const int dx4[] = {1, -1, 0, 0}, dy4[] = {0, 0, -1, 1};
const int dx8[] = {1, -1, 0, 0, 1, -1, 1, -1}, dy8[] = {0, 0, -1, 1, 1, -1, -1, 1};
int64_t n, k, arr[mxN], par[mxN], cost[mxN], ans = 0;
vector<int> g[mxN];
bool vis[mxN];
void dfs(int u) {
if (!vis[u])
cost[u] += arr[u];
vis[u] = true;
int mn = INT_MAX, node = -1;
for (auto &v : g[u]) {
if (vis[v]) continue;
// cout << "----------------------\n";
// cout << "From: " << u << "\n";
// cout << "Total Cost for node u: " << cost[u] << "\n";
// cout << "To: " << v << "\n";
// cout << "Cost of node v: " << arr[v] << "\n";
// cout << "Requared cost: " << cost[u] + arr[v] << "\n";
if (cost[u] + arr[v] <= k) {
if (mn > arr[v]) {
mn = arr[v];
node = v;
}
} else {
ans++;
dfs(v);
}
}
if (node != -1) {
// cout << node << " " << mn << "\n";
// cout << "Minimal cost:\n";
// cout << "From: " << u << "\n";
// cout << "Total Cost for node u: " << cost[u] << "\n";
// cout << "To: " << node << "\n";
// cout << "Cost of node v: " << arr[node] << "\n";
// cout << "Requared cost: " << cost[u] + arr[node] << "\n";
par[node] = u;
cost[node] = cost[u];
dfs(node);
}
// cout << "Leaf node: \n";
// cout << u << " " << cost[u] << " " << par[u] << "\n";
cost[par[u]] = cost[u];
// cout << cost[par[u]] << "\n";
if (par[u] != u)
dfs(par[u]);
}
void run_case() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> arr[i], par[i] = i;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
// cout << "Output:\n";
dfs(1);
// cout << "\n";
cout << ans << "\n";
// cout << "Visited: ";
// for (int i = 1; i <= n; i++) cout << vis[i] << " ";
// cout << "\n";
// cout << "Cost: ";
// for (int i = 1; i <= n; i++) cout << cost[i] << " ";
return;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int test_case = 1;
// cin >> test_case;
for (int num_case = 1; num_case <= test_case; num_case++) {
run_case();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |