Submission #1295897

#TimeUsernameProblemLanguageResultExecution timeMemory
1295897avighnaCat in a tree (BOI17_catinatree)C++20
0 / 100
1 ms1024 KiB
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, d;
  cin >> n >> d;
  vector<vector<int>> adj(n);
  for (int i = 1, p; i < n; ++i) {
    cin >> p;
    adj[p].push_back(i);
  }

  if (d >= n) {
    cout << "1\n";
    return 0;
  }

  // dp[u][d] = in the subtree of u, nodes are at least d away from the root
  auto dfs = [&](auto &&self, int u) -> vector<int> {
    vector<int> ch_dp(n), dp(n);
    int sum = 0;
    for (int &i : adj[u]) {
      vector<int> res = self(self, i);
      sum += res[d - 1];
      for (int d = 0; d < n; ++d) {
        for (int l = 0; l <= d; ++l) {
          dp[d] = max(dp[d], ch_dp[l] + res[d - l]);
        }
      }
      for (int i = 0; i < n; ++i) {
        ch_dp[i] += res[i];
      }
    }
    dp[0] = max(dp[0], sum + 1);
    return dp;
  };

  auto dp = dfs(dfs, 0);
  cout << dp[0] << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...