제출 #1254101

#제출 시각아이디문제언어결과실행 시간메모리
1254101kaiboyCat in a tree (BOI17_catinatree)C++20
100 / 100
51 ms19272 KiB
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int   N = 200000;
const int INF = 0x3f3f3f3f;

vector<int> ej[N];
int kk[N], dd[N], d_;

void dfs(int i) {
	int k = 0, d = 0, e = INF;
	for (int j : ej[i]) {
		dfs(j);
		k += kk[j];
		if (dd[j] + 1 < (d_ + 1) / 2)
			k--, d = max(d, dd[j] + 1);
		else
			e = min(e, dd[j] + 1);
	}
	if (d + e >= d_) {
		kk[i] = k + 1;
		dd[i] = d;
	} else {
		kk[i] = k;
		dd[i] = e;
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n >> d_;
	for (int i = 1; i < n; i++) {
		int p; cin >> p;
		ej[p].push_back(i);
	}
	dfs(0);
	cout << kk[0] << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...