Submission #1322856

#TimeUsernameProblemLanguageResultExecution timeMemory
1322856am_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 {
		int ans = 0;
		for (int root = 0; root < n; ++root) {
			vector<int> lvl(n), cnt(n);
			vector<bool> vis(n, 0);
			queue<int> q; q.push(root);
			lvl[root] = 0; ++cnt[root], vis[root] = 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]));
			ans = max(ans, dp[0]);
		}
		cout << ans;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...