1056D. Decorate Apple Tree - Codeforces Solution C++

➤  Problem Link : 1056D. Decorate Apple Tree 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

int ans[100001]={0};

int dfs(int v,vector<int> adj[], int n,int p)
{
	if(adj[v].size()==1 && p!=-1)  //leaf
	{
		ans[1]++;
		return 1;
	}

	int cnt=0;
	for(int i=0;i<adj[v].size();i++)
	{
		if(adj[v][i]==p)
			continue;
		cnt+=dfs(adj[v][i],adj,n,v);
	}
	ans[cnt]++;
	return cnt;
}


int main()
{
	int n,v;
	cin>>n;
	if(n==1)
	{
	    cout<<"1";
	    exit(0);
	}
	vector<int> adj[n+1];
	for(int i=2;i<=n;i++)
	{
		cin>>v;
		adj[i].push_back(v);
		adj[v].push_back(i);
	}

	dfs(1,adj,n,-1);
    
    
    
	vector<int> vec;

	int junc=1;
	int ind=1;
	int sum=0;
	while(junc<=n)
	{
		if(sum+ans[ind]>=junc)
		{
			vec.push_back(ind);
			junc++;
		}
		else
		{
		    sum+=ans[ind];
			ind++;
		}
	}           

	for(auto i: vec)
		cout<<i<<" ";

}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.