Submission #314687

#TimeUsernameProblemLanguageResultExecution timeMemory
314687TemmieCat in a tree (BOI17_catinatree)C++17
100 / 100
120 ms20856 KiB
#include <bits/stdc++.h>

int n, d, ans = 0;
std::vector <std::vector <int>> g;

int dfs(int node = 0, int par = -1) {
	std::vector <int> sub;
	for (int x : g[node]) if (x != par) sub.push_back(dfs(x, node));
	if (sub.empty()) return ++ans * 0 + 1;
	std::sort(sub.rbegin(), sub.rend());
	int close = sub.front();
	for (size_t i = 1; i < sub.size(); i++) {
		ans -= sub[i] + close < d;
		if (close + sub[i] >= d) close = sub[i];
	}
	ans += close >= d;
	return 1 + close - d * (close >= d);
}

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	std::cin >> n >> d;
	g.resize(n);
	for (int i = 0; i < n - 1; i++) {
		int p; std::cin >> p;
		g[i + 1].push_back(p);
		g[p].push_back(i + 1);
	}
	dfs();
	std::cout << ans << "\n";
	std::cout.flush(); std::cin >> n;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...