제출 #1305619

#제출 시각아이디문제언어결과실행 시간메모리
1305619ghos007Cat in a tree (BOI17_catinatree)C++20
51 / 100
27 ms30268 KiB
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
#define int long long
using namespace std;
const int MAXN = 2000;
int dp[MAXN][MAXN];
void dfs(int u,int p,vector <vector <int>> &g,int d) {
  dp[u][0] = 1;
  vector <int> perehod(MAXN);
  for (auto el : g[u]) {
    if (el == p)continue;
    dfs(el,u,g,d);
    dp[u][0] = dp[u][0] + dp[el][d-1];
    for (int i = 1;i <= d;i++) {
      int v1 = max(d - i,i);
      dp[u][i] = max(dp[u][i] + dp[el][v1 - 1],dp[u][v1] + dp[el][i-1]);
    }
    for (int i = d - 1;i >= 0;i--) {
      dp[u][i] = max(dp[u][i],dp[u][i+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);
  }
  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();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...