Codeforces div2-C

https://codeforces.com/problemset/problem/1336/A

using namespace std;

vector<vector<int>> adj;
bool visited[20006];
int height[20006];
void dfs(int node,int level)
{
    visited[node]=true;
    for(int i=0;i<adj[node].size();i++)
    {
        if(!visited[adj[node][i]])
        {
            height[adj[node][i]]=height[node]+1;
            dfs(adj[node][i],height[adj[node][i]]);
        }
    }
}

int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        height[i]=0;
        visited[i]=false;
    }
    for(int i=0;i<n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1,0);
    sort(height,height+n);
    int i=n-1;
    int hap=0;
    while(k>0)
    {
        hap+=height[i];
        i--;
        k--;
    }
    cout<<hap<<"\n";

}

why this approach is wrong?
I am trying to store the height of each level in an array and sorting it and calculating the happiness!

your code will not give correct output for the first sample testcase if k=5,in this case answer should be 7 but a/t your logic it will give 8,this is because if you select some non leaf as industry city,then happiness of all the child of this node will decreases by 1 which you are not considering.

1 Like