Submission #1117762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117762		vjudge1	Paprike (COI18_paprike)	C++17	100 / 100	43 ms	19984 KiB

paprike

#include<bits/stdc++.h>
using namespace std;
vector<int>g[100001];
long long dp[100001],val[100001];
long long k;
int ans;
void dfs(int n,int p)
{
    dp[n]=val[n];
    vector<int>v;
    for(int g:g[n])
    {
        if(g!=p)
        {
            dfs(g,n);
            dp[n]+=dp[g];
            v.push_back(dp[g]);
        }
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    int ind=0;
    while(dp[n]>k)
    {
        ans++;
        dp[n]-=v[ind];
        ind++;
    }
}
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);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}

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