stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define N 100000

using namespace std;



int child[N][20];

int parent[N];

int depth[N];

int k[N];

int root;



char str[3][20] = {"root","internal node","leaf"};



void pr(int id){

  int type;

  if(parent[id] == -1) type = 0;

  else if(k[id] > 0) type = 1;

  else if(k[id] == 0) type = 2;



  

  printf("node %d: parent = %d, depth = %d, %s, [", id, parent[id], depth[id], str[type]);

  for(int i=0;i<k[id];i++){

    if(i)printf(", ");

    printf("%d",child[id][i]);

  }

  printf("]\n");

}



void dfs(int id,int dep){

  depth[id] = dep;

  for(int i=0;i<k[id];i++)dfs(child[id][i],dep+1);

}



int main(){

  int n;

  cin>>n;

  memset(parent,-1,sizeof(parent));

  for(int i=0,id;i<n;i++){

    cin>>id;

    cin>>k[id];

    for(int j=0;j<k[id];j++){

      cin>>child[id][j];

      parent[ child[id][j] ] = id;

    }

  }

  

  for(int i=0;i<n;i++) if(parent[i] == -1) root = i;

  dfs(root,0);

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



  return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#define MAX 100005

#define NIL -1

struct Node_struct{int p, l, r;};

typedef struct Node_struct Node;

Node T[MAX];

int n, D[MAX];



void print(int u){

  int i, c;

  printf("node %d: parent = %d, depth = %d, ", u, T[u].p, D[u]);

  if(T[u].p == NIL) printf("root, ");

  else if(T[u].l == NIL) printf("leaf, ");

  else printf("internal node, ");

  printf("[");

  for (i =0, c = T[u].l; c != NIL; i++, c = T[c].r){

    if(i) printf(", ");

    printf("%d", c);

  }

  printf("]\n");

}



void rec(int u, int p){

  D[u] = p;

  if(T[u].l != NIL) rec(T[u].l, p + 1);

  if(T[u].r != -1) rec(T[u].r, p);

}



int main(){

  int i, j, k;

  int N;

  int id, sib, child;

  int root = NIL;

  scanf("%d", &N);

  for(i=0;i<N;i++) T[i].p = T[i].l = T[i].r = NIL;

  

  for(i=0; i<N; i++){

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

    for(j =0, sib= NIL; j<k; j++){

      scanf("%d", &child);

      T[child].p = id;

      if(j == 0) T[id].l = child;

      else T[sib].r = child;

      sib = child;

    }

  }



  for(i=0; i<N; i++){

    if(T[i].p == -1) root = i;

  }

  rec(root, 0);

  for(i=0; i<N; i++) print(i);

  

  return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <vector>

#pragma warning(disable : 4996)

using namespace std;

int n, id, c, p[100009], d[100009]; vector<int> child[100009]; bool vis[100009];

void rec(int pos) {

	vis[pos] = true;

	for (int i : child[pos]) rec(i);

}

void solve(int pos) {

	for (int i : child[pos]) {

		d[i] = d[pos] + 1;

		p[i] = pos;

		solve(i);

	}

}

int main() {

	scanf("%d", &n);

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

		scanf("%d%d", &id, &c);

		child[id].resize(c);

		for (int j = 0; j < c; j++) {

			scanf("%d", &child[id][j]);

		}

	}

	int root = -1;

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

		if (!vis[i]) {

			root = i;

			rec(i);

		}

	}

	solve(root); p[root] = -1;

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

		printf("node %d: parent = %d, depth = %d, %s, [", i, p[i], d[i], (i == root ? "root" : (child[i].size() ? "internal node" : "leaf")));

		for (int j = 0; j < child[i].size(); j++) {

			if (j) printf(", ");

			printf("%d", child[i][j]);

		}

		printf("]\n");

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

// ----- very fast input/output ----- //

int read_int() {

	char ch = getchar_unlocked();

	int res = 0;

	while('0' <= ch && ch <= '9') {

		res = res * 10 + ch - '0';

		ch = getchar_unlocked();

	}

	return res;

}

void print_str(const char* str) {

	while(*str != '\0') {

		putchar_unlocked(*str);

		++str;

	}

}

char buf[1024];

void print_int(int x) {

	if(x < 0) {

		putchar_unlocked('-');

		x *= -1;

	}

	int ptr = 0, g;

	do {

		g = x / 10;

		buf[ptr++] = x - g * 10;

		x = g;

	} while(x > 0);

	while(ptr--) {

		putchar_unlocked(buf[ptr] + '0');

	}

}

// ----- main part ----- //

int N, sep[102400], dst[102400], depth[102400], par[102400];

int inputs[307200];

void find_depth(int pos) {

	for(int i = sep[pos]; i < sep[pos + 1]; ++i) {

		depth[dst[i]] = depth[pos] + 1;

		find_depth(dst[i]);

	}

}

int main() {

	// #1. read input

	N = read_int();

	for(int i = 0; i < 3 * N - 1; ++i) {

		inputs[i] = read_int();

	}

	// #2. construct tree

	int curpos = 0;

	for(int i = 0; i < N; ++i) {

		sep[inputs[curpos] + 1] = inputs[curpos + 1];

		curpos += inputs[curpos + 1] + 2;

	}

	for(int i = 0; i < N; ++i) {

		sep[i + 1] += sep[i];

	}

	curpos = 0;

	int root = 0;

	for(int i = 0; i < N; ++i) {

		int id = inputs[curpos];

		for(int j = sep[id]; j < sep[id + 1]; ++j) {

			dst[j] = inputs[curpos + j - sep[id] + 2];

			par[dst[j]] = id;

			root ^= dst[j];

		}

		root ^= i;

		curpos += inputs[curpos + 1] + 2;

	}

	par[root] = -1;

	find_depth(root);

	// step #3. print the answer

	for(int i = 0; i < N; ++i) {

		print_str("node ");

		print_int(i);

		print_str(": parent = ");

		print_int(par[i]);

		print_str(", depth = ");

		print_int(depth[i]);

		print_str(i == root ? ", root, [" : (sep[i] == sep[i + 1] ? ", leaf, [" : ", internal node, ["));

		for(int j = sep[i]; j < sep[i + 1]; ++j) {

			if(j != sep[i]) print_str(", ");

			print_int(dst[j]);

		}

		print_str("]\n");

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <stdio.h>

#include <vector>

using namespace std;



struct Node{

	int parent;

	int depth;

	vector<int> children;

};



void solve(vector<struct Node> &node, int x){

	for(int i=0;i<node[x].children.size();i++){

		node[node[x].children[i]].depth += node[x].depth + 1;

		solve(node, node[x].children[i]);

	}

}



void printNode(vector<struct Node> node, int n){

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

		cout<<"node "<<i<<": parent = "<<node[i].parent<<", depth = "<<node[i].depth<<", ";

		

		if(node[i].parent == -1)

			cout<<"root";

		else if(node[i].children.size() == 0)

			cout<<"leaf";

		else

			cout<<"internal node";



		cout<<", [";

		for(int j=0;j<node[i].children.size();j++){

			cout<<node[i].children[j];

			if(j != node[i].children.size()-1)

				cout<<", ";

		}

		cout<<"]"<<endl;

	}

}



int main(){

	int n, id, k, c, x;

	vector<struct Node> node(100000);



	cin>>n;

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

		node[i].parent = -1;

		node[i].depth = 0;

	}



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

		cin>>id>>k;

		

		for(int j=0;j<k;j++){

			cin>>c;

			node[id].children.push_back(c);

			node[c].parent = id;

		}

	}



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

		if(node[i].parent == -1)

			x = i;



	solve(node, x);

	printNode(node, n);

	return 0;

}

// Optimized solution to the same problem (faster):
// ALDS1_7_A

#include <iostream>

#include <vector>

using namespace std;



struct Node {

	int parent;

	int depth;

	vector<int> children;

};



void cal_depth(vector<Node> &Tree, int p) {

	if (Tree[p].parent != -1)

		Tree[p].depth = Tree[Tree[p].parent].depth + 1;



	for (int i = 0; i < Tree[p].children.size(); i++)

		cal_depth(Tree, Tree[p].children[i]);

}



void printTree(vector<Node> Tree) {

	for (int i = 0; i < Tree.size(); i++) {

		cout <<"node "<< i << ": parent = " << Tree[i].parent << ", depth = " << Tree[i].depth << ", ";

		

		if (Tree[i].parent == -1)

			cout << "root, ";

		else if (Tree[i].children.size() == 0)

			cout << "leaf, ";

		else

			cout << "internal node, ";

		

		cout << "[";

		for (int j = 0; j < Tree[i].children.size(); j++) {

			cout << Tree[i].children[j];

			if (j != Tree[i].children.size() - 1)

				cout << ", ";

		}

		cout << "]" << endl;

	}

}



int main() {

	

	int n, id, c, k, root;

	cin >> n;



	vector<Node> Tree;



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

		Node node;

		node.parent = -1;

		node.depth = 0;

		Tree.push_back(node);

	}



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

		cin >> id >> k;

		

		for (int j = 0; j < k; j++) {

			cin >> c;

			Tree[c].parent = id;

			Tree[id].children.push_back(c);

		}

	}



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

		if (Tree[i].parent == -1)

			root = i;

	}



	cal_depth(Tree, root);



	printTree(Tree);



	return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <queue>

#include <vector>

#include <utility>



#define rep(i, n) REP(i, 0, n)

#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

#define pb push_back

#define NIL -1

#define MAX 100001



using namespace std;



struct Node{

  int id;

  int parent;

  vector<int> child;

  int depth;

  

  void addChild(int c){

    child.pb(c);

  }

    

 void print(){

    cout << "node " << id << ": ";

    cout << "parent = " << parent << ", ";

    cout << "depth = " << depth << ", ";

    cout << (parent == -1?"root":child.size()==0?"leaf":"internal node") << ", ";

    cout << "[";

    if(child.size() != 0){

      rep(i, child.size()-1){

    cout << child[i] << ", ";

      }

      cout << child[child.size()-1];

    }

      cout << "]" << endl;

 }

};



Node node[MAX];



void init(int n){

  rep(i, n){

    node[i].depth = NIL;

    node[i].parent = NIL;

    node[i].child.clear();    

  }

}



signed main(){

  int n;

  int id, k, c, root;

  cin >> n;

  init(n);

  

  root = NIL;



  rep(i, n){

    cin >> id >> k;

    node[id].id = id;

    rep(j, k){

      cin >> c;

      node[id].addChild(c);

      node[c].parent = id;

      node[c].depth = node[id].depth + 1;

    }

  }



  rep(i, n){

    if(node[i].parent == NIL){

      root = i;

      break;

    }

  }

  

  queue<pair<Node, int> > q;

  q.push(make_pair(node[root], -1));

  while(!(q.empty())){

    pair<Node, int> p = q.front(); q.pop();

    node[p.first.id].depth = p.second + 1;

    rep(i, p.first.child.size()){

      q.push(make_pair(node[p.first.child[i]], p.second + 1));

    }

  }

  

  rep(i, n){

    node[i].print();

  }

}

// Optimized solution to the same problem (faster):
#include<iostream>

using namespace std;

#define MAX 100005

#define NIL -1



struct Node{int p,l,r;};



Node T[MAX];

int n,D[MAX];



void print(int u){

  int i,c;

  cout << "node " << u<<": ";

  cout <<"parent = " << T[u].p << ", ";

  cout << "depth = " << D[u] <<", ";

  

  if(T[u].p==NIL)cout<<"root, ";

  else if(T[u].l==NIL)cout<<"leaf, ";

  else cout <<"internal node, ";

  

  cout<<"[";

  

  for (i = 0,c=T[u].l;c!=NIL;i++,c=T[c].r) {

    if(i)cout <<", ";

    cout<<c;

  }

  cout <<"]"<<endl;

}



//再帰的に深さを求める

int rec(int u,int p){

  D[u] =p;

  if(T[u].r!=NIL)rec(T[u].r,p); //右の兄弟に同じ深さを設定

  if(T[u].l!=NIL)rec(T[u].l,p+1); //もっとも左の子に自分の深さ+1を設定

  return 0;

}



int main(){

  int i,j,d,v,c,l,r;

  cin >> n;

  for(i=0;i<n;i++)T[i].p=T[i].l=T[i].r=NIL;

  

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

    cin>>v>>d;

    for(j=0;j<d;j++){

      cin>>c;

      if(j==0)T[v].l=c;

      else T[l].r=c;

      l=c;

      T[c].p=v;

    }

  } 

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

    if(T[i].p==NIL)r=i;

  }

  

  rec(r,0);

  

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

    print(i);

  }

  

  return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}






// Optimized solution to the same problem (faster):
#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;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}	

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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);

}

// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
//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;

}




// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//2018.9.29 by ljz

#include<bits/stdc++.h>

using namespace std;

#define res register int

#define LL long long

#define inf 0x3f3f3f3f

#define eps 1e-15

inline int read(){

    res s=0;

    bool w=0;

    char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}

    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();

    return w?-s:s;

}

inline void _swap(res &x,res &y){

    x^=y^=x^=y;

}

inline int _abs(const res &x){

    return x>0?x:-x;

}

inline int _max(const res &x,const res &y){

    return x>y?x:y;

}

inline int _min(const res &x,const res &y){

    return x<y?x:y;

}

const int N=1e5+10;

namespace MAIN{

    int n,k;

    int fa[N];

    struct E{

        int next,to;

        E() {}

        E(res next,res to):next(next),to(to) {}

    }edge[N];

    int head[N],cnt;

    inline void addedge(const res &u,const res &v){

        edge[++cnt]=E(head[u],v),head[u]=cnt;

    }

    int ans;

    int dfs(const res &x,const res &depx){

        res ret=depx;

        for(res i=head[x];~i;i=edge[i].next){

            res tox=edge[i].to;

            ret=_max(ret,dfs(tox,depx+1));

        }

        if(fa[x]!=1&&ret-depx==k-1){ans++;return 0;}

        return ret;

    }

    inline void MAIN(){

        memset(head,-1,sizeof(head));

        n=read(),k=read();

        for(res i=1;i<=n;i++)fa[i]=read();

        for(res i=2;i<=n;i++)addedge(fa[i],i);

        if(fa[1]!=1)ans++;

        fa[1]=1;

        dfs(1,0);

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

    }

}

int main(){

    MAIN::MAIN();

    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

const int maxn=100000+10;

int n,k,a[maxn],f[maxn],head[maxn],to[maxn],nxt[maxn],tot,ans;



void add(int x,int y){

	to[++tot]=y;

	nxt[tot]=head[x];

	head[x]=tot;

}



void dfs(int x){

	for(int i=head[x],y;i;i=nxt[i]){

		y=to[i];

		dfs(y);

		f[x]=max(f[x],f[y]+1);

	}

	if(f[x]==k-1&&a[x]!=1){

		f[x]=-1;

		ans++;

	}

}



int main()

{

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

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

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

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

		add(a[i],i);

	}

	if(a[1]!=1){

		ans++;

		a[1]=1;

	}

	dfs(1);

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

	return 0;

}

// Fastest known solution for this problem: