Submission #869248

---

Source Code Expand

#include<bits/stdc++.h>

typedef long long LL;  
using namespace std;

#define fillchar(a, x) memset(a, x, sizeof(a))
#define MP make_pair
#define PB push_back
#define endl '\n'

const int M = 1000000007;
const int N = 1e5 + 5;

int par[N];
int he[N];
bool color[N];
int n;

void dfs(int s)
{
color[s] = true;

if(!color[par[s]])
	dfs(par[s]);

if(s!=0)
	he[s] = he[par[s]] + 1;
else
	he[0] = 0;
}

int main()
{
ios_base::sync_with_stdio(0); 
cout.precision(15);
cout.setf(ios::fixed);

int k;
int i,j;

cin>>n>>k;

bool allone = true;

for(i=0;i<n;i++)
	{
	cin>>par[i];
	par[i]--;	
	}


int cnt = 0;

if(par[0]!= 0)
	{par[0] = 0;cnt = 1;}

for(i=0;i<n;i++)
	if(!color[i])
		dfs(i);


// for(i=0;i<n;i++)
// 	cout<<i+1<<' '<<he[i]<<endl;

vector <pair<int,int> > v(n);

for(i=0;i<n;i++)
	{
	v[i].first = he[i];	
	v[i].second = i;
	}

sort(v.begin(),v.end());

for(i=1;i<n;i++)
	{
	int hh = he[par[v[i].second]] + 1;	

	if(hh > k)
		{
		par[v[i].second] = 0;	
		cnt++;
		}
	he[v[i].second] = he[par[v[i].second]] + 1;
	}

cout<<cnt<<endl;

}

Submission Info

Judge Result