Submission #1322855

#TimeUsernameProblemLanguageResultExecution timeMemory
1322855am_aadvikCat in a tree (BOI17_catinatree)C++20
0 / 100
1 ms332 KiB
#include<iostream>
#include<vector>
#include<queue>
const int maxn = 2e5;
using namespace std;

vector<int> g[maxn];
int dp[maxn][2];
int dfs(int node, int par, bool t) {
	if (t == 0) {
		for (auto x : g[node])
			if (x != par)
				dfs(x, node, 0), dfs(x, node, 1),
				dp[node][t] += max(dp[x][0], dp[x][1]);
	}
	else {
		dp[node][t] = dp[node][0];
		for (auto x : g[node])
			if (x != par)
				dp[node][t] += dfs(x, node, 0);
	}
	return dp[node][t];
}
int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, d; cin >> n >> d;
	for (int i = 1; i < n; ++i) {
		int x; cin >> x;
		g[x].push_back(i);
		g[i].push_back(x);
	}
	if (d == 1) { cout << n; return 0; }
	else if (d == 2) {
		dfs(0, -1, 0); dfs(0, -1, 1);
		cout << max(dp[0][0], dp[0][1]);
	}
	else {
		vector<int> lvl(n), cnt(n);
		vector<bool> vis(n, 0);
		queue<int> q; q.push(0);
		lvl[0] = 0; ++cnt[0], vis[0] = 1;
		while (!q.empty()) {
			int node = q.front(); q.pop();
			for (auto x : g[node])
				if (!vis[x]) {
					lvl[x] = lvl[node] + 1;
					vis[x] = 1; q.push(x);
					++cnt[lvl[x]];
				}
		}
		vector<int> a;
		for (int i = 0; i < n; ++i)
			if (!cnt[i]) break;
			else a.push_back(cnt[i]);
		vector<int> dp(a.size() + d, 0);
		for (int i = a.size() - 1; i >= 0; --i)
			dp[i] = max(dp[i + 1], dp[i + d] + (i ? a[i - 1] : a[i]));
		cout << dp[0];
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...