제출 #1127165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127165		fryingduc	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	281 ms	156216 KiB

catinatree

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n, k;
vector<int> g[maxn];

deque<long long> dq[maxn];
void dfs(int u) {
  dq[u].push_back(1);
  for(auto v:g[u]) {
    dfs(v);

    dq[v].push_front(dq[v].front());
    if((int)dq[v].size() > (int)dq[u].size()) {
      dq[u].swap(dq[v]);
    }
    for(int i = 0; i < (int)dq[v].size(); ++i) {
      long long x = dq[v][i] + (max(i, k - i + 1) < (int)dq[u].size() ? dq[u][max(i, k - i + 1)] : 0);
      long long y = dq[u][i] + (max(i, k - i + 1) < (int)dq[v].size() ? dq[v][max(i, k - i + 1)] : 0);

      dq[u][i] = max(dq[u][i], max(x, y));
    }
    for(int i = (int)dq[v].size() - 1; i >= 0; --i) {
      if(i + 1 < (int)dq[u].size()) {
        dq[u][i] = max(dq[u][i], dq[u][i + 1]);
      }
    }
    dq[v].clear();
  }    
}
void solve() {  
  cin >> n >> k;
  for(int i = 2; i <= n; ++i) {
    int p; cin >> p;
    ++p;
    g[p].push_back(i);
  }
  if(k > n) {
    cout << 1;
    return;
  }
  if(k == 0) {
    cout << n;
    return;
  }
  --k;
  dfs(1);
  cout << dq[1][0];
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();

  return 0;
}

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