When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Xenomorphing_19's blog

By Xenomorphing_19, history, 3 years ago, In English

I have written the following code for the problem Linova and Kingdom I am getting a WA on some test cases. I am unable to identify the error. Please help me out.

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
vector <ll> vec[200006],contri(200006,0),sub(200006,1);
void solve(ll node, ll parent, ll level)
{
    int cnt=0;
    for(auto it:vec[node])
    {
        if(it!=parent)
        {
            solve(it,node,level+1);
            cnt+=sub[it];
        }
    }
    sub[node]+=cnt;
    contri[node] = level-sub[node];
}
int main()
{
    ll n,k;
    cin>>n>>k;
    for(ll i=0;i<n-1;i++)
    {
        ll u,v;
        cin>>u>>v;
        vec[v].pb(u);
        vec[u].pb(v);
    }
    solve(1,0,1);
    sort(contri.begin(),contri.end(),greater<ll>());
    ll ans=0;
    for(ll i=0;i<k;i++)
    {
        ans+=contri[i];
    }
    cout<<ans;
}

Thanks in advance