Submission #1513333

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int INF = 1145141919;

vector<int> g[100010];
int N, K;
int ans = 0;

void dfs(int cur, vector<int>& dist) {
	for (int nex : g[cur]) {
		if (dist[nex] != INF) continue;
		dist[nex] = dist[cur] + 1;
		if (dist[nex] > K) {
			ans++;
			dist[nex] = 1;
		}
		dfs(nex, dist);
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> N >> K;
	vector<int> a(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		a[i]--;
	}

	for (int i = 1; i < N; i++) {
		g[a[i]].push_back(i);
	}

	vector<int> dist(N, INF);
	dist[0] = 0;
	ans += (a[0] != 0);
	dfs(0, dist);

	for (int i = 1; i < N; i++) {
		if (dist[i] == INF) {
			ans++;
			dist[i] = 1;
			dfs(i, dist);
		}
	}

	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result