# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
465437 | osmanallazov | Paprike (COI18_paprike) | C++14 | 122 ms | 17448 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;
long long n,k;
long long ans=0;
long long val[100005];
long long a[100005];
long long b[100005];
vector<long long>qraf[100005];
int dfs(long long x, long long par){
vector<long long>v;
for(long long i=0;i<(long long)(qraf[x]).size();i++){
long long child=qraf[x][i];
if(child==par)
continue;
v.push_back(dfs(child,x));
}
sort(v.begin(),v.end());
long long sum=0;
for(long long i=0;i<v.size();i++)
sum += v[i];
for(long long i=v.size()-1;i>=0;i--){
if(sum>k){
sum-=v[i];
ans++;
}
else{break;}
}
return sum;
}
int main (){
cin>>n>>k;
for(int i=0; i<n; i++){
cin>>val[i];
}
for(int i=0; i<n-1; i++){
cin>>a[i]>>b[i];
qraf[a[i]].push_back(b[i]);
qraf[b[i]].push_back(a[i]);
}
dfs(1,0);
cout<<ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |