Submission #1305631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305631		ghos007	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	286 ms	271400 KiB

catinatree

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
#define int long long
using namespace std;
const int MAXN = 2e5 + 1;
deque <int> dp[MAXN];
int h[MAXN],max_h[MAXN];
void dfs(int u,int p,vector <vector <int>> &g,int d) {
  dp[u] = {1};
  for (auto el : g[u]) {
    if (el == p)continue;
    dfs(el,u,g,d);
  }
  if (max_h[u] == -1) {
    return;
  }
  swap(dp[u],dp[max_h[u]]);
  dp[u].push_front(1);
  if (dp[u].size() > d) {
    dp[u][0] += dp[u][d];
  }
  dp[u][0] = max(dp[u][0],dp[u][1]);
  while (dp[u].size() > d + 1) {
    dp[u].pop_back();
  }
  for (auto el : g[u]) {
    if (el == p || el == max_h[u]) {
      continue;
    }
    if (dp[el].size() > d - 1) {
      dp[u][0] = dp[u][0] + dp[el][d-1];
    }
    for (int i = 0;i < dp[el].size();i++) {
      int di = i + 1;
      int v1 = max(di,d - di);
      int var1 = 0,var2 = 0;
      if (dp[u].size() > v1) {
        var1 = dp[el][di - 1] + dp[u][v1];
      }else {
        var1 = dp[el][di-1];
      }
      if (dp[el].size() > v1 - 1) {
        var2 = dp[el][v1-1] + dp[u][di];
      }else {
        var2 = dp[u][di];
      }
      dp[u][di] = max(var1,var2);
    }
    for (int i = dp[el].size();i >= 0 ;i--) {
      int di = i + 1;
      if (di + 1 < dp[u].size())dp[u][di] = max(dp[u][di],dp[u][di + 1]);
    }
    dp[u][0] = max(dp[u][0],dp[u][1]);
  }
}
int dfs1(int u,int p,vector <vector <int>> &g) {
  max_h[u] = -1;
  for (auto el : g[u]) {
    if (el == p)continue;
    int h_now = dfs1(el,u,g);
    if (h_now > h[u]) {
      max_h[u] = el;
      h[u] = h_now;
    }
  }
  return h[u] + 1;
}
void solve() {
  int n,d;
  cin >> n >> d;
  vector <vector <int>> g(n);
  d = min(n,d);
  for (int i = 1;i < n;i++) {
    int x;
    cin >> x;
    g[x].push_back(i);
  }
  dfs1(0,-1,g);
  dfs(0,-1,g,d);
  int best = 0;
  for (auto el : dp[0]) {
    best = max(best,el);
  }
  cout << best << "\n";
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  solve();
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49