Submission #44351

#	Time	Username	Problem	Language	Result	Execution time	Memory
44351		aleksami	Paprike (COI18_paprike)	C++14	100 / 100	116 ms	44992 KiB

paprike

#include <bits/stdc++.h>

using namespace std;
#define MAXN 100005
long long a[MAXN];
long long sz[MAXN];
vector <int> g[MAXN];
int n,k;
int ans=0;

void dfs(int v,int p)
{
	sz[v]=a[v];
	vector <long long> vals;
	for(auto x:g[v])
	{
		if(x!=p)
		{
			dfs(x,v);
			sz[v]+=sz[x];
			vals.push_back(sz[x]);
		}
	}
	sort(vals.begin(),vals.end());
	auto it = vals.end();
	it--;
	while(sz[v]>k)
	{
		sz[v]-=*it;
		ans++;
		it--;
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin >> n >> k;
	for(int i = 1; i <= n; i++)cin >> a[i];
	for(int i = 0; i < n-1; i++)
	{
		int u,v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	cout << ans;
	return 0;
}

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