# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1117614 | vjudge1 | Paprike (COI18_paprike) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
vector<int>g[100001];
bool visit[100001];
long long val[100001];
int ans=0;
long long k,sum;
void dfs(int node)
{
sum+=val[node];
if(sum<=k)
{
visit[node]=1;
for(int go:g[node])
if(!visit[go])
dfs(go);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>val[i];
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
for(int i=1;i<=n;i++)
{
if(visit[i]==0)
{
ans++;
dfs(i);
sum=0;
}
}
cout<<ans-1;
return 0;
}