Submission #976674

#TimeUsernameProblemLanguageResultExecution timeMemory
976674Halym2007Cat in a tree (BOI17_catinatree)C++17
100 / 100
72 ms24916 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define sz size()
const int N = 2e5 + 5;
pii dp[N];
vector <int> v[N];
int n, d;
void solve (int x) {
	dp[x] = {0, d};
	int val = 0;
	vector <int> q;
	for (int i : v[x]) {
		solve (i);
		val += dp[i].ff;
		q.pb (dp[i].ss + 1);
	}
	sort (q.begin(), q.end());
	for (int i = 0; i < (int)q.sz; ++i) {
		int j = lower_bound (q.begin(), q.end(), d - q[i]) - q.begin();
		if (i < j) j--;
		else {
			j = i;
		}
		dp[x] = max (dp[x], {val - j, q[i]});
	}
	if (dp[x].ss >= d) {
		dp[x].ff++;
		dp[x].ss = 0;
	}
}


int main () {
	cin >> n >> d;
	for (int i = 1; i < n; ++i) {
		int par;
		cin >> par;
		v[par].pb (i);
	}
	solve (0);
	cout << dp[0].ff;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...