Submission #1142998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142998		ezzzay	Paprike (COI18_paprike)	C++20	13 / 100	64 ms	18248 KiB

paprike

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int h[N];
vector<int>v[N];
int n,k;
int sbtr[N];
int ans=0;
void dfs(int a,int p){
	sbtr[a]+=h[a];
	for(auto b:v[a]){
		if(b==p)continue;
		dfs(b,a);
		if(sbtr[b]+sbtr[a]>k){
			ans++;
		}
		else{
			sbtr[a]+=sbtr[b];
		}
	}
}	
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>h[i];
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	dfs(1,0);
	cout<<ans;
}

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