Submission #1115895

#TimeUsernameProblemLanguageResultExecution timeMemory
1115895BuzzyBeezCat in a tree (BOI17_catinatree)C++17
0 / 100
2 ms6648 KiB
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[200008];
pair<int, int> dp[200008];
int D;

void DFS(int u) {
	vector<int> Q;
	for (int v : adj[u]) {
		DFS(v); dp[u].first += dp[v].first;
		Q.push_back(dp[v].second + 1);
	}
	sort(Q.begin(), Q.end(), greater<>());
	if (Q.empty()) dp[u] = {1, 0};
	else if (Q.size() == 1) {
		if (dp[u].second >= D) ++dp[u].first, dp[u].second = 0;
		else dp[u].second = Q[0];
	}
	else {
		while (Q.size() > 1 && Q[Q.size() - 1] + Q[Q.size() - 2] < D) --dp[u].first, Q.pop_back();
		dp[u].second = Q.back();
		if (dp[u].second >= D) ++dp[u].first, dp[u].second = 0;
	}
	// cout << u << ' ' << dp[u].first << ' ' << dp[u].second << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, u, v; cin >> n >> D;
	for (u = 1; u < n; ++u) cin >> v, adj[v].push_back(u);
	DFS(0); cout << dp[0].first;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...