Problem- 1336A Linova and kingdom DFS

Revision en2, by Xenomorphing_19, 2021-03-07 10:07:53

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

Tags #dfs, #trees, #dfs and similar

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Xenomorphing_19 2021-03-07 10:07:53 21
en1 English Xenomorphing_19 2021-03-07 10:06:42 1036 Initial revision (published)