Submission #1316484

#TimeUsernameProblemLanguageResultExecution timeMemory
1316484pastaCat in a tree (BOI17_catinatree)C++20
100 / 100
116 ms12180 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define S  second
#define F  first
#define all(x)		(x).begin(),(x).end()
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;


int n, d, par[maxn];
vector<int> g[maxn];
pii dp[maxn];

bool cmp(int v, int u) {
	return dp[v].S < dp[u].S;
}

void dfs(int v) {
	dp[v] = {1, 0};
	for (int u : g[v]) {
		dfs(u);
	}
//	sort(all(g[v]));
	for (int u : g[v]) {	
		if (dp[v].S + dp[u].S + 1 >= d) {
			dp[v] = {dp[v].F + dp[u].F, min(dp[v].S, dp[u].S + 1)};
		}
		else {
			dp[v] = {dp[v].F + dp[u].F - 1, max(dp[v].S, dp[u].S + 1)};
		}
	}
}

signed main() {
	cin >> n >> d;
	for (int i = 1; i < n; i++) {
		int p; cin >> p;
		g[p].pb(i);
	}
	dfs(0);
	cout << dp[0].F << '\n';
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...