Submission #913912

#	Time	Username	Problem	Language	Result	Execution time	Memory
913912		ParsaS	Paprike (COI18_paprike)	C++17	100 / 100	38 ms	22044 KiB

paprike

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;

const int N = 2e5 + 5;
int n, k, h[N];
int ans, dp[N];
vector<int> adj[N];

void dfs(int v, int p) {
	dp[v] = h[v];
	vector<int> vec;
	for (auto u : adj[v]) {
		if (u != p) {
			dfs(u, v);
			vec.pb(dp[u]);
		}
	}
	sort(vec.begin(), vec.end());
	ans += (int)vec.size();
	for (int i = 0; i < (int)vec.size() && vec[i] + dp[v] <= k; dp[v] += vec[i], i++, ans--);
}

void solve() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> h[i];
	for (int i = 0; i < n - 1; i++) {
		int v, u; cin >> v >> u;
		adj[v].pb(u), adj[u].pb(v);
	}
	dfs(1, 0);
	cout << ans << endl;
}

int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int tc = 1; // cin >> tc;
	while (tc--) {
		solve();
	}

	return 0;
}

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