Submission #232776

#	Time	Username	Problem	Language	Result	Execution time	Memory
232776		pedy4000	Paprike (COI18_paprike)	C++14	100 / 100	90 ms	17144 KiB

paprike

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const int N = 1e5 + 5;
int n, k, ans;
int Arr[N];
vector <int> G[N];

int dfs (int v, int par = 0) {
	vector <int> vec;
	ll sum = 0;

	for (int u: G[v])
		if (u != par) {
			vec.push_back(dfs(u, v));
			sum += vec.back();
		}
	sum += Arr[v];
	sort(vec.begin(), vec.end());
	while (k < sum) {
		sum -= vec.back();
		ans++;
		vec.pop_back();
	}
	return sum;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> Arr[i];

	for (int i = 0; i < n - 1; i++) {
		int v, u;
		cin >> v >> u;
		v--, u--;

		G[v].push_back(u);
		G[u].push_back(v);
	}

	dfs(0);
	cout << ans << "\n";
	return 0;
}

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