Submission #314687

#	Time	Username	Problem	Language	Result	Execution time	Memory
314687		Temmie	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	120 ms	20856 KiB

catinatree

#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;
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49