제출 #1275547

#제출 시각아이디문제언어결과실행 시간메모리
1275547rtriCat in a tree (BOI17_catinatree)C++20
11 / 100
7 ms584 KiB
#include <bits/stdc++.h>
using namespace std;

int n, d;
vector<vector<int>> adj;

pair<int, int> dfs(int u, int p = -1) {
  vector<pair<int, int>> c;
  for (int v : adj[u])
    if (v != p) {
      auto [ans, length] = dfs(v, u);
      c.push_back({length, ans});
    }
  sort(c.begin(), c.end());
  reverse(c.begin(), c.end());

  int ans = 0, length = d;
  for (auto [l, a] : c) {
    if (d <= l + length) {
      ans += a;
      length = l;
    } else
      break;
  }

  if (d <= length) {
    ans++;
    length = 0;
  }

  cerr << u << " " << ans << " " << length + 1 << endl;

  return {ans, length + 1};
}

int main() {
  cin >> n >> d;

  adj.resize(n);
  for (int u = 1; u < n; u++) {
    int v;
    cin >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  auto [ans, length] = dfs(0);

  cout << ans << endl;

  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...