#include <bits/stdc++.h>
using namespace std;
const int kN = 1e5;
const int kLog = 19;
const int kInf = 1e9;
int dep[kN], tin[kN];
vector<int> adj[kN], rmq[kLog];
void dfs(int u) {
tin[u] = rmq[0].size();
rmq[0].emplace_back(u);
for(const auto &v: adj[u]) {
dfs(v);
rmq[0].emplace_back(u);
}
}
int minNode(int u, int v) {
if(dep[u] < dep[v]) return u;
return v;
}
int lca(int u, int v) {
int l = tin[u], r = tin[v];
if(l > r) swap(l, r);
int lg = __lg(r - l + 1);
return minNode(rmq[lg][l], rmq[lg][r - (1 << lg) + 1]);
}
int dist(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
void minSelf(int &x, int y) {
if(y < x) {
x = y;
}
}
int sz[kN];
bitset<kN> rem;
void findSizes(int u) {
sz[u] = 1;
for(const auto &v: adj[u]) if(!rem[v]) {
findSizes(v);
sz[u] += sz[v];
}
}
int findCentroid(int u, int desired) {
for(const auto &v: adj[u]) if(!rem[v] && sz[v] > desired) {
return findCentroid(v, desired);
}
return u;
}
int up[kN], best[kN];
void buildTree(int u, int p = -1) {
findSizes(u);
int c = findCentroid(u, sz[u] >> 1);
rem[c] = true;
up[c] = p;
for(const auto &v: adj[c]) if(!rem[v]) {
buildTree(v, c);
}
}
int findClosest(int u) {
int res = kInf, v = u;
while(v != -1) {
minSelf(res, best[v] + dist(u, v));
assert(v != up[v]);
v = up[v];
}
return res;
}
void updateClosest(int u) {
int v = u;
while(v != -1) {
minSelf(best[v], dist(u, v));
assert(v != up[v]);
v = up[v];
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, d;
cin >> n >> d;
for(int i = 1; i < n; i++) {
int x;
cin >> x;
adj[x].emplace_back(i);
dep[i] = dep[x] + 1;
}
rmq[0].reserve(n << 1);
dfs(0);
for(int i = 1; (1 << i) < n << 1; i++) {
for(int j = 0; j + (1 << i) - 1 < 2 * n - 1; j++) {
rmq[i].emplace_back(minNode(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]));
}
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&] (int u, int v) {
return dep[u] > dep[v];
});
fill(best, best + n, kInf);
fill(up, up + n, -1);
buildTree(0);
int ans = 0;
for(const auto &u: ord) {
int closest = findClosest(u);
if(closest >= d) {
ans++;
updateClosest(u);
}
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
