stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<cstdlib>

#include<string>

using namespace std;



int n;



struct node

{

	int id, pid, bid, k, d;

	int* cid;

	string type;

}N[100005];



void GetDepth(node& GN)

{

	GN.d = 0;

	node temp = GN;



	while (temp.pid != -1)

	{

		GN.d++;

		temp = N[temp.pid];

	}

}



void GetType(node& GN)

{

	if (GN.pid == -1)

		GN.type = "root";

	else if (GN.k == 0)

		GN.type = "leaf";

	else

		GN.type = "internal node";

}



void print()

{

	for (int i = 0; i < n; i++)

	{

		cout << "node " << N[i].id << ": " << "parent = " << N[i].pid << ", " << "depth = " << N[i].d << ", " << N[i].type << ", " << "[";



		if (N[i].k != 0)

		{

			for (int j = 0; j < N[i].k - 1; j++)

				cout << N[i].cid[j] << ", ";

			cout << N[i].cid[N[i].k - 1];

		}



		cout << "]" << endl;

	}	

}



int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);



	int place;

	cin >> n;

	

	for (int i = 0; i < n; i++)

		N[i].pid = -1;

	

	for (int i = 0; i < n; i++)

	{

		cin >> place;

		N[place].id = place;

		cin >> N[place].k;



		if (N[place].k > 0)

			N[place].cid = (int*)malloc(sizeof(int) * N[place].k);



		for (int j = 0; j < N[place].k; j++)

		{

			cin >> N[place].cid[j];

			N[N[place].cid[j]].pid = N[place].id;

		}			

	}



	for (int i = 0; i < n; i++)

		GetDepth(N[i]);



	for (int i = 0; i < n; i++)

		GetType(N[i]);	



	print();



	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 1.1291031232404045x):
#include<iostream>

#include<string>

using namespace std;



int n;



struct node

{

	int id, pid, k, d;

	int* cid;

	string type;

}N[100005];



void GetDepth(node& GN)

{

	GN.d = 0;

	node temp = GN;



	while (temp.pid != -1)

	{

		GN.d++;

		temp = N[temp.pid];

	}

}



void GetType(node& GN)

{

	if (GN.pid == -1)

		GN.type = "root";

	else if (GN.k == 0)

		GN.type = "leaf";

	else

		GN.type = "internal node";

}



void print()

{

	for (int i = 0; i < n; i++)

	{

		cout << "node " << N[i].id << ": " << "parent = " << N[i].pid << ", " << "depth = " << N[i].d << ", " << N[i].type << ", " << "[";



		if (N[i].k != 0)

		{

			for (int j = 0; j < N[i].k - 1; j++)

				cout << N[i].cid[j] << ", ";

			cout << N[i].cid[N[i].k - 1];

		}



		cout << "]" << endl;

	}	

}



int main()

{

	//ios::sync_with_stdio(false);

	//cin.tie(0);



	int place;

	cin >> n;

	

	for (int i = 0; i < n; i++)

		N[i].pid = -1;

	

	for (int i = 0; i < n; i++)

	{

		cin >> place;

		N[place].id = place;

		cin >> N[place].k;



		if (N[place].k > 0)

			N[place].cid = new int[N[place].k];



		for (int j = 0; j < N[place].k; j++)

		{

			cin >> N[place].cid[j];

			N[N[place].cid[j]].pid = N[place].id;

		}			

	}



	for (int i = 0; i < n; i++)

		GetDepth(N[i]);



	for (int i = 0; i < n; i++)

		GetType(N[i]);	



	print();



	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdlib>

#include<string>

using namespace std;



int n;



struct node

{

	int id, pid, bid, k, d;

	int* cid;

	string type;

}N[100005];



void GetDepth(node& GN)

{

	GN.d = 0;

	node temp = GN;



	while (temp.pid != -1)

	{

		GN.d++;

		temp = N[temp.pid];

	}

}



void GetType(node& GN)

{

	if (GN.pid == -1)

		GN.type = "root";

	else if (GN.k == 0)

		GN.type = "leaf";

	else

		GN.type = "internal node";

}



void print()

{

	for (int i = 0; i < n; i++)

	{

		cout << "node " << N[i].id << ": " << "parent = " << N[i].pid << ", " << "depth = " << N[i].d << ", " << N[i].type << ", " << "[";



		if (N[i].k != 0)

		{

			for (int j = 0; j < N[i].k - 1; j++)

				cout << N[i].cid[j] << ", ";

			cout << N[i].cid[N[i].k - 1];

		}



		cout << "]" << endl;

	}	

}



int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);



	int place;

	cin >> n;

	

	for (int i = 0; i < n; i++)

		N[i].pid = -1;

	

	for (int i = 0; i < n; i++)

	{

		cin >> place;

		N[place].id = place;

		cin >> N[place].k;



		if (N[place].k > 0)

			N[place].cid = (int*)malloc(sizeof(int) * N[place].k);



		for (int j = 0; j < N[place].k; j++)

		{

			cin >> N[place].cid[j];

			N[N[place].cid[j]].pid = N[place].id;

		}			

	}



	for (int i = 0; i < n; i++)

		GetDepth(N[i]);



	for (int i = 0; i < n; i++)

		GetType(N[i]);	



	print();



	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 1.1252637708530548x):
#include<iostream>

#include<string>

using namespace std;



int n;



struct node

{

	int id, pid, k, d;

	int* cid;

	string type;

}N[100005];



void GetDepth(node& GN)

{

	GN.d = 0;

	node temp = GN;



	while (temp.pid != -1)

	{

		GN.d++;

		temp = N[temp.pid];

	}

}



void GetType(node& GN)

{

	if (GN.pid == -1)

		GN.type = "root";

	else if (GN.k == 0)

		GN.type = "leaf";

	else

		GN.type = "internal node";

}



void print()

{

	for (int i = 0; i < n; i++)

	{

		cout << "node " << N[i].id << ": " << "parent = " << N[i].pid << ", " << "depth = " << N[i].d << ", " << N[i].type << ", " << "[";



		if (N[i].k != 0)

		{

			for (int j = 0; j < N[i].k - 1; j++)

				cout << N[i].cid[j] << ", ";

			cout << N[i].cid[N[i].k - 1];

		}



		cout << "]" << endl;

	}	

}



int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);



	int place;

	cin >> n;

	

	for (int i = 0; i < n; i++)

		N[i].pid = -1;

	

	for (int i = 0; i < n; i++)

	{

		cin >> place;

		N[place].id = place;

		cin >> N[place].k;



		if (N[place].k > 0)

			N[place].cid = new int[N[place].k];



		for (int j = 0; j < N[place].k; j++)

		{

			cin >> N[place].cid[j];

			N[N[place].cid[j]].pid = N[place].id;

		}			

	}



	for (int i = 0; i < n; i++)

		GetDepth(N[i]);



	for (int i = 0; i < n; i++)

		GetType(N[i]);	



	print();



	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdlib>

#include<string>

using namespace std;



int n;



struct node

{

	int id, pid, bid, k, d;

	int* cid;

	string type;

}N[100005];



void GetDepth(node& GN)

{

	GN.d = 0;

	node temp = GN;



	while (temp.pid != -1)

	{

		GN.d++;

		temp = N[temp.pid];

	}

}



void GetType(node& GN)

{

	if (GN.pid == -1)

		GN.type = "root";

	else if (GN.k == 0)

		GN.type = "leaf";

	else

		GN.type = "internal node";

}



void print()

{

	for (int i = 0; i < n; i++)

	{

		cout << "node " << N[i].id << ": " << "parent = " << N[i].pid << ", " << "depth = " << N[i].d << ", " << N[i].type << ", " << "[";



		if (N[i].k != 0)

		{

			for (int j = 0; j < N[i].k - 1; j++)

				cout << N[i].cid[j] << ", ";

			cout << N[i].cid[N[i].k - 1];

		}



		cout << "]" << endl;

	}	

}



int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);



	int place;

	cin >> n;

	

	for (int i = 0; i < n; i++)

		N[i].pid = -1;

	

	for (int i = 0; i < n; i++)

	{

		cin >> place;

		N[place].id = place;

		cin >> N[place].k;



		if (N[place].k > 0)

			N[place].cid = (int*)malloc(sizeof(int) * N[place].k);



		for (int j = 0; j < N[place].k; j++)

		{

			cin >> N[place].cid[j];

			N[N[place].cid[j]].pid = N[place].id;

		}			

	}



	for (int i = 0; i < n; i++)

		GetDepth(N[i]);



	for (int i = 0; i < n; i++)

		GetType(N[i]);	



	print();



	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 1.125184807119819x):
#include<iostream>

#include<string>

using namespace std;



int n;



struct node

{

	int id, pid, k, d;

	int* cid;

	string type;

}N[100005];



void GetDepth(node& GN)

{

	GN.d = 0;

	node temp = GN;



	while (temp.pid != -1)

	{

		GN.d++;

		temp = N[temp.pid];

	}

}



void GetType(node& GN)

{

	if (GN.pid == -1)

		GN.type = "root";

	else if (GN.k == 0)

		GN.type = "leaf";

	else

		GN.type = "internal node";

}



void print()

{

	for (int i = 0; i < n; i++)

	{

		cout << "node " << N[i].id << ": " << "parent = " << N[i].pid << ", " << "depth = " << N[i].d << ", " << N[i].type << ", " << "[";



		if (N[i].k != 0)

		{

			for (int j = 0; j < N[i].k - 1; j++)

				cout << N[i].cid[j] << ", ";

			cout << N[i].cid[N[i].k - 1];

		}



		cout << "]" << endl;

	}	

}



int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);



	int place;

	cin >> n;

	

	for (int i = 0; i < n; i++)

		N[i].pid = -1;

	

	for (int i = 0; i < n; i++)

	{

		cin >> place;

		N[place].id = place;

		cin >> N[place].k;



		if (N[place].k > 0)

			N[place].cid = new int[N[place].k];



		for (int j = 0; j < N[place].k; j++)

		{

			cin >> N[place].cid[j];

			N[N[place].cid[j]].pid = N[place].id;

		}			

	}



	for (int i = 0; i < n; i++)

	{

		GetDepth(N[i]);

		GetType(N[i]);

	}



	print();



	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

using namespace __gnu_pbds;



#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fbo find_by_order

#define ook order_of_key



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<int> vi;

typedef long double ld; 

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef set<int>::iterator sit;

typedef map<int,int>::iterator mit;

typedef vector<int>::iterator vit;



int a[100001];

vi adj[100001];

int h[100001];

int ans, k;



void dfs(int u, int p)

{

	h[u] = 1;

	for(int i = 0; i < adj[u].size(); i++)

	{

		int v = adj[u][i];

		dfs(v, u);

		h[u] = max(h[u], h[v] + 1);

	}

	if(u != 1 && p != 1 && h[u] >= k)

	{

		ans++; h[u] = 0;

	}

}



int main()

{

	ios_base::sync_with_stdio(0); cin.tie(0);

	int n; cin >> n >> k;

	for(int i = 1; i <= n; i++)

	{

		cin >> a[i];

	}

	ans = 0;

	if(a[1] != 1)

	{

		a[1] = 1;

		ans++;

	}

	for(int i = 2; i <= n; i++)

	{

		adj[a[i]].pb(i);

	}

	//now we have a tree

	dfs(1, -1);

	cout << ans;

}	

// Faster C++ solution for the same problem (measured speedup: 18.56514579162581x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 100000

using namespace std;

typedef long long LL;

struct node

{

	int to;

	node *nxt;

}edges[MAXN+5];

node *ncnt=&edges[0],*Adj[MAXN+5];

int a[MAXN+5],N,dep[MAXN+5],dep2[MAXN+5],K,maxdep[MAXN+5];

LL ans=0;

void AddEdge(int u,int v)

{

	node *p=++ncnt;

	p->to=v;

	p->nxt=Adj[u];

	Adj[u]=p;

}

void DFS(int u)

{

	dep[u]=1;

	for(node *p=Adj[u];p!=NULL;p=p->nxt)

	{

		int v=p->to;

		DFS(v);

		dep[u]=max(dep[u],dep[v]+1);

	}

	if(dep[u]==K&&a[u]!=1)

	{

		ans++;

		dep[u]=0;

	}

}

int main()

{

	scanf("%d %d",&N,&K);

	for(int i=1;i<=N;i++)

		scanf("%d",&a[i]);

	if(a[1]!=1)

		a[1]=1,ans+=1LL;

	for(int i=2;i<=N;i++)

		AddEdge(a[i],i);

	DFS(1);

	printf("%lld\n",ans);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

using namespace __gnu_pbds;



#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fbo find_by_order

#define ook order_of_key



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<int> vi;

typedef long double ld; 

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef set<int>::iterator sit;

typedef map<int,int>::iterator mit;

typedef vector<int>::iterator vit;



int a[100001];

vi adj[100001];

int h[100001];

int ans, k;



void dfs(int u, int p)

{

	h[u] = 1;

	for(int i = 0; i < adj[u].size(); i++)

	{

		int v = adj[u][i];

		dfs(v, u);

		h[u] = max(h[u], h[v] + 1);

	}

	if(u != 1 && p != 1 && h[u] >= k)

	{

		ans++; h[u] = 0;

	}

}



int main()

{

	ios_base::sync_with_stdio(0); cin.tie(0);

	int n; cin >> n >> k;

	for(int i = 1; i <= n; i++)

	{

		cin >> a[i];

	}

	ans = 0;

	if(a[1] != 1)

	{

		a[1] = 1;

		ans++;

	}

	for(int i = 2; i <= n; i++)

	{

		adj[a[i]].pb(i);

	}

	//now we have a tree

	dfs(1, -1);

	cout << ans;

}	

// Faster C++ solution for the same problem (measured speedup: 3.600563095369609x):
#include <bits/stdc++.h>



using namespace std;



#ifdef Lin1043

    #define DEBUG(msg, ...) printf("(%s #%d) " msg, __FUNCTION__, __LINE__, __VA_ARGS__)

    #define massert(...) assert(...)

#else

    #define DEBUG(...)

    #define massert(...)

#endif



#define rep(i , l , r) for(int i = (l) , ___ = (r) ; i <= ___ ; ++i )

#define per(i , r , l) for(int i = (r) , ___ = (l) ; i >= ___ ; --i )



struct iopener

{

    iopener()

    {

#ifdef Lin1043

        freopen("./in" , "r" , stdin);

#endif

    }

} iop;



typedef long long LL;



template<typename T>inline bool chkmin(T &x , const T &y) { return x > y ? (x = y , 1) : 0; }

template<typename T>inline bool chkmax(T &x , const T &y) { return x < y ? (x = y , 1) : 0; }



template<typename T>inline T read(T &f)

{

    f = 0; int x = 1 ; char c = getchar();

    while(!isdigit(c)) x = (c == '-' ? -1 : 1) , c = getchar();

    while(isdigit(c)) (f *= 10) += c & 15 , c = getchar();

    return f = x * f;

}



const int N = 100000 + 5;



int n , m , u , v , Ans , A[N] , dep[N];



struct Edge

{

    int to ; Edge *nxt;

} E[N << 1] , *pre[N];



void addedge(int u , int v)

{

    static int tot = 0;

    E[++tot] = (Edge){v , pre[u]} , pre[u] = &E[tot];

    E[++tot] = (Edge){u , pre[v]} , pre[v] = &E[tot];

}



void dfs(int u , int fa)

{

    dep[u] = 1;

    for(Edge *i = pre[u] ; i ; i = i->nxt)

    {

        int v = i->to;

        if(v == fa) continue ;

        dfs(v , u); //  , u);

        chkmax(dep[u] , dep[v] + 1);

    }

    if(dep[u] >= m && A[u] != 1)

    {

        Ans++ , dep[u] = 0;

    }

}



int main()

{

    read(n) , read(m);

    rep(i , 1 , n)

    {

        read(v) , u = i ;

        A[i] = v;

        if(i != 1) addedge(v , u);

    }

    if(A[1] != 1) Ans++ , A[1] = 1;

    dfs(1 , 0);

    cout << Ans << endl;

    return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=100005;

int ans=0,n,k;

vector<int>w[MAXN];

bool vis[MAXN];

int dfs(int u,int f)

{

	int re=0;

	for(int i=0;i<int(w[u].size());i++)

	{

		int v=w[u][i];

		if(v!=f)

		{

			re=max(re,dfs(v,u));

		}

	}

	re++;

	if(vis[u]==0&&re>=k)

	{

		if(re>k)

			printf("HJB!");

		re=0;

		ans++;

	}

	return re;

}

int main()

{

	scanf("%d %d",&n,&k);

	int a;

	scanf("%d",&a);

	if(a!=1)

		ans=1;

	for(int i=2;i<=n;i++)

	{

		scanf("%d",&a);

		w[a].push_back(i);

		w[i].push_back(a);

		if(a==1)

			vis[i]=1;

	}

	vis[1]=1;

	dfs(1,0);

	printf("%d\n",ans);

}

// Faster C++ solution for the same problem (measured speedup: 3.4910839496670176x):
#include <bits/stdc++.h>



using namespace std;



#ifdef Lin1043

    #define DEBUG(msg, ...) printf("(%s #%d) " msg, __FUNCTION__, __LINE__, __VA_ARGS__)

    #define massert(...) assert(...)

#else

    #define DEBUG(...)

    #define massert(...)

#endif



#define rep(i , l , r) for(int i = (l) , ___ = (r) ; i <= ___ ; ++i )

#define per(i , r , l) for(int i = (r) , ___ = (l) ; i >= ___ ; --i )



struct iopener

{

    iopener()

    {

#ifdef Lin1043

        freopen("./in" , "r" , stdin);

#endif

    }

} iop;



typedef long long LL;



template<typename T>inline bool chkmin(T &x , const T &y) { return x > y ? (x = y , 1) : 0; }

template<typename T>inline bool chkmax(T &x , const T &y) { return x < y ? (x = y , 1) : 0; }



template<typename T>inline T read(T &f)

{

    f = 0; int x = 1 ; char c = getchar();

    while(!isdigit(c)) x = (c == '-' ? -1 : 1) , c = getchar();

    while(isdigit(c)) (f *= 10) += c & 15 , c = getchar();

    return f = x * f;

}



const int N = 100000 + 5;



int n , m , u , v , Ans , A[N] , dep[N];



struct Edge

{

    int to ; Edge *nxt;

} E[N << 1] , *pre[N];



void addedge(int u , int v)

{

    static int tot = 0;

    E[++tot] = (Edge){v , pre[u]} , pre[u] = &E[tot];

    E[++tot] = (Edge){u , pre[v]} , pre[v] = &E[tot];

}



void dfs(int u , int fa)

{

    dep[u] = 1;

    for(Edge *i = pre[u] ; i ; i = i->nxt)

    {

        int v = i->to;

        if(v == fa) continue ;

        dfs(v , u); //  , u);

        chkmax(dep[u] , dep[v] + 1);

    }

    if(dep[u] >= m && A[u] != 1)

    {

        Ans++ , dep[u] = 0;

    }

}



int main()

{

    read(n) , read(m);

    rep(i , 1 , n)

    {

        read(v) , u = i ;

        A[i] = v;

        if(i != 1) addedge(v , u);

    }

    if(A[1] != 1) Ans++ , A[1] = 1;

    dfs(1 , 0);

    cout << Ans << endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

using namespace __gnu_pbds;



#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fbo find_by_order

#define ook order_of_key



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<int> vi;

typedef long double ld; 

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef set<int>::iterator sit;

typedef map<int,int>::iterator mit;

typedef vector<int>::iterator vit;



int a[100001];

vi adj[100001];

int h[100001];

int ans, k;



void dfs(int u, int p)

{

	h[u] = 1;

	for(int i = 0; i < adj[u].size(); i++)

	{

		int v = adj[u][i];

		dfs(v, u);

		h[u] = max(h[u], h[v] + 1);

	}

	if(u != 1 && p != 1 && h[u] >= k)

	{

		ans++; h[u] = 0;

	}

}



int main()

{

	ios_base::sync_with_stdio(0); cin.tie(0);

	int n; cin >> n >> k;

	for(int i = 1; i <= n; i++)

	{

		cin >> a[i];

	}

	ans = 0;

	if(a[1] != 1)

	{

		a[1] = 1;

		ans++;

	}

	for(int i = 2; i <= n; i++)

	{

		adj[a[i]].pb(i);

	}

	//now we have a tree

	dfs(1, -1);

	cout << ans;

}	

// Faster C++ solution for the same problem (measured speedup: 3.587356838238494x):
#include <map>

#include <list>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

using namespace std;



int to[100005],nxt[100005],hed[100005] = {0},ec = 0;

void add_edge(int f,int t){

	ec ++; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec;

}



int n,k,a[100005],ans = 0;



int dfs(int v,int dep){

	int tmp = dep;

	for(int i = hed[v];i;i = nxt[i]){

		tmp = max(tmp,dfs(to[i],dep + 1));

	}

	if(a[v] != 1 && tmp - dep == k - 1){

		a[v] = 1;

		ans ++;

		return -1;

	}

	return tmp;

}



int main(){

	scanf("%d %d",&n,&k);

	scanf("%d",&a[1]); if(a[1] != 1) ans ++; a[1] = 1;

	for(int i = 2;i <= n;i ++){

		scanf("%d",&a[i]);

		add_edge(a[i],i);

	}

	dfs(1,0);

        cout << ans << endl;

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=100005;

int ans=0,n,k;

vector<int>w[MAXN];

bool vis[MAXN];

int dfs(int u,int f)

{

	int re=0;

	for(int i=0;i<int(w[u].size());i++)

	{

		int v=w[u][i];

		if(v!=f)

		{

			re=max(re,dfs(v,u));

		}

	}

	re++;

	if(vis[u]==0&&re>=k)

	{

		if(re>k)

			printf("HJB!");

		re=0;

		ans++;

	}

	return re;

}

int main()

{

	scanf("%d %d",&n,&k);

	int a;

	scanf("%d",&a);

	if(a!=1)

		ans=1;

	for(int i=2;i<=n;i++)

	{

		scanf("%d",&a);

		w[a].push_back(i);

		w[i].push_back(a);

		if(a==1)

			vis[i]=1;

	}

	vis[1]=1;

	dfs(1,0);

	printf("%d\n",ans);

}

// Faster C++ solution for the same problem (measured speedup: 3.478279243546216x):
#include <map>

#include <list>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

using namespace std;



int to[100005],nxt[100005],hed[100005] = {0},ec = 0;

void add_edge(int f,int t){

	ec ++; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec;

}



int n,k,a[100005],ans = 0;



int dfs(int v,int dep){

	int tmp = dep;

	for(int i = hed[v];i;i = nxt[i]){

		tmp = max(tmp,dfs(to[i],dep + 1));

	}

	if(a[v] != 1 && tmp - dep == k - 1){

		a[v] = 1;

		ans ++;

		return -1;

	}

	return tmp;

}



int main(){

	scanf("%d %d",&n,&k);

	scanf("%d",&a[1]); if(a[1] != 1) ans ++; a[1] = 1;

	for(int i = 2;i <= n;i ++){

		scanf("%d",&a[i]);

		add_edge(a[i],i);

	}

	dfs(1,0);

        cout << ans << endl;

	return 0;

}
// Slower C++ solution:
//By Don4ick 

//#define _GLIBCXX_DEBUG



#include <bits/stdc++.h>



typedef long long ll;

typedef long double ld;

typedef unsigned int ui;



#define forn(i, n) for (int i = 1; i <= n; i++)

#define pb push_back

#define all(x) x.begin(), x.end()

#define y1 qewr1234



const double PI = acos(-1.0);

const int DIR = 4;

const int X[] = {1, 0, -1, 0};

const int Y[] = {0, 1, 0, -1};



const int N = (int)1e5 + 228;



using namespace std;



int n, k, depth[N], a[N], ans;

vector < int > g[N];



void dfs(int v, int pr)

{

	for (auto to : g[v])

	{

		if (to == pr)

			continue;

		dfs(to, v);

		if (v != 1 && depth[to] + 1 == k)

		{

			ans++;

		}

		else

			depth[v] = max(depth[v], depth[to] + 1);

	}

}



int main()

{

	//ios_base::sync_with_stdio(false);

	//cin.tie();

	//cout.tie();		



	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);



	//~read

	scanf("%d%d", &n, &k);

	forn(i, n)

		scanf("%d", &a[i]);

	//~solve

	if (a[1] != 1)

		ans++;

	for (int i = 2; i <= n; i++)

		g[a[i]].pb(i);

	dfs(1, -1);

	cout << ans << endl;



	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 3.568873508949507x):
#include <map>

#include <list>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

using namespace std;



int to[100005],nxt[100005],hed[100005] = {0},ec = 0;

void add_edge(int f,int t){

	ec ++; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec;

}



int n,k,a[100005],ans = 0;



int dfs(int v,int dep){

	int tmp = dep;

	for(int i = hed[v];i;i = nxt[i]){

		tmp = max(tmp,dfs(to[i],dep + 1));

	}

	if(a[v] != 1 && tmp - dep == k - 1){

		a[v] = 1;

		ans ++;

		return -1;

	}

	return tmp;

}



int main(){

	scanf("%d %d",&n,&k);

	scanf("%d",&a[1]); if(a[1] != 1) ans ++; a[1] = 1;

	for(int i = 2;i <= n;i ++){

		scanf("%d",&a[i]);

		add_edge(a[i],i);

	}

	dfs(1,0);

        cout << ans << endl;

	return 0;

}