Submission #1293369

#TimeUsernameProblemLanguageResultExecution timeMemory
1293369LIACat in a tree (BOI17_catinatree)C++17
100 / 100
241 ms66112 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (int i = s; i < e; ++i)
v<v<int>> g;
int n, d;
v<int> sz, mark, best;
v<v<pair<int, int>>> dists;
const int inf = 1e7;
inline int f_sz(int node, int par) {
  sz[node] = 1;
  for (int it : g[node]) {
    if (it != par && !mark[it]) {
      sz[node] += f_sz(it, node);
    }
  }
  return sz[node];
}

inline int find(int node, int par, int nodes) {
  for (int it : g[node]) {
    if (it != par && !mark[it]) {
      if (sz[it] > nodes / 2)
        return find(it, node, nodes);
    }
  }
  return node;
}

inline void add(int node, int par, int cen, int dis) {
  dists[node].push_back({cen, dis});
  for (int it : g[node]) {
    if (it != par && !mark[it]) {
      add(it, node, cen, dis + 1);
    }
  }
}

inline void build(int node, int par) {
  int nodes = f_sz(node, par);
  int cen = find(node, par, nodes);
  mark[cen] = 1;
  add(cen, -1, cen, 0);
  for (int it : g[cen]) {
    if (it != par && !mark[it]) {
      build(it, cen);
    }
  }
}

inline void update(int node) {
  for (auto &[cen, dis] : dists[node]) {
    best[cen] = min(best[cen], dis);
  }
}

inline int query(int node) {
  int ans = inf;
  for (auto &[cen, dis] : dists[node]) {
    ans = min(dis + best[cen], ans);
  }
  return ans;
}

v<pair<int, int>> dists2;

void dfs2(int node, int par, int dis) {
  dists2.push_back({-dis, node});
  for (auto it : g[node]) {
    if (it != par) {
      dfs2(it, node, dis + 1);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> d;
  g.resize(n);
  sz.resize(n);
  best.resize(n, inf);
  dists.resize(n);
  mark.resize(n);
  lp(i, 1, n) {
    int a, b = i;
    cin >> a;
    // a--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  build(0, -1);

  dfs2(0, -1, 0);
  int ans = 0;
  v<int> nodes;
  sort(dists2.begin(), dists2.end());
  for (auto [dis, node] : dists2) {
    int md = query(node);
    if (md >= d) {
      ans++;
      update(node);
      nodes.push_back(node);
    }
  }
  cout << ans << '\n';
  // for (auto it : nodes)
  //   cout << it + 1 << " ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...