#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 998244353
#define LOGN 18
#define MAXN 200005
vector<int> graph[MAXN];
vector<int> par, sz, nearest;
int up[LOGN][MAXN], depth[MAXN];
bool marked[MAXN];
void dfs(int node, int parent) {
for (auto u : graph[node]) {
if (u == parent)
continue;
depth[u] = depth[node] + 1;
up[0][u] = node;
for (int i = 1; i < LOGN; i++)
up[i][u] = up[i-1][up[i-1][u]];
dfs(u, node);
}
}
int find(int node, int k) {
for (int i = 0; i < LOGN; i++) {
if ((1<<i) & k)
node = up[i][node];
}
return node;
}
int lca(int a, int b) {
if (depth[b] > depth[a])
swap(a, b);
a = find(a, depth[a] - depth[b]);
if (a == b)
return a;
for (int i = LOGN-1; i >= 0; i--) {
if (up[i][a] != up[i][b]) {
a = up[i][a];
b = up[i][b];
}
}
return up[0][a];
}
int dist(int a, int b) {
return depth[a] + depth[b] - 2*depth[lca(a, b)];
}
int get_sz(int node, int parent) {
for (auto u : graph[node]) {
if (u == parent || marked[u])
continue;
sz[node] += get_sz(u, node);
}
return sz[node];
}
int find_centro(int node, int parent, int n) {
for (auto u : graph[node]) {
if (u == parent || marked[u])
continue;
if (sz[u] * 2 > n)
return find_centro(u, node, n);
}
return node;
}
void decompose(int node, int parent) {
int n = get_sz(node, parent);
int centro = find_centro(node, node, n);
par[centro] = parent;
marked[centro] = true;
for (auto u : graph[centro]) {
if (!marked[u])
decompose(u, centro);
}
}
int main() {
int N, D;
cin >> N >> D;
nearest = vector<int>(N, 1e9);
par = vector<int>(N, -1);
sz = vector<int>(N, 1);
for (int i = 1; i < N; i++) {
int x; cin >> x;
graph[x].push_back(i);
graph[i].push_back(x);
}
for (int i = 0; i < LOGN; i++)
up[i][0] = 0;
dfs(0, 0);
decompose(0, -1);
vector<pair<int,int>> order;
for (int i = 0; i < N; i++)
order.push_back({depth[i], i});
sort(order.rbegin(), order.rend());
int ans = 0;
for (auto u : order) {
int node = u.s;
int now = node;
int mn_dist = 1e9;
while (now != -1) {
mn_dist = min(mn_dist, dist(node, now) + nearest[now]);
now = par[now];
}
if (mn_dist >= D) {
ans++;
int now = node;
while (now != -1) {
nearest[now] = min(nearest[now], dist(node, now));
now = par[now];
}
}
}
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5008 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5076 KB |
Output is correct |
5 |
Correct |
3 ms |
5076 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
2 ms |
5076 KB |
Output is correct |
8 |
Correct |
3 ms |
5076 KB |
Output is correct |
9 |
Correct |
3 ms |
5076 KB |
Output is correct |
10 |
Correct |
2 ms |
5004 KB |
Output is correct |
11 |
Correct |
3 ms |
5004 KB |
Output is correct |
12 |
Correct |
2 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
2 ms |
5004 KB |
Output is correct |
16 |
Correct |
3 ms |
5076 KB |
Output is correct |
17 |
Correct |
3 ms |
5076 KB |
Output is correct |
18 |
Correct |
3 ms |
5076 KB |
Output is correct |
19 |
Correct |
3 ms |
5112 KB |
Output is correct |
20 |
Correct |
3 ms |
5076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5008 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5076 KB |
Output is correct |
5 |
Correct |
3 ms |
5076 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
2 ms |
5076 KB |
Output is correct |
8 |
Correct |
3 ms |
5076 KB |
Output is correct |
9 |
Correct |
3 ms |
5076 KB |
Output is correct |
10 |
Correct |
2 ms |
5004 KB |
Output is correct |
11 |
Correct |
3 ms |
5004 KB |
Output is correct |
12 |
Correct |
2 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
2 ms |
5004 KB |
Output is correct |
16 |
Correct |
3 ms |
5076 KB |
Output is correct |
17 |
Correct |
3 ms |
5076 KB |
Output is correct |
18 |
Correct |
3 ms |
5076 KB |
Output is correct |
19 |
Correct |
3 ms |
5112 KB |
Output is correct |
20 |
Correct |
3 ms |
5076 KB |
Output is correct |
21 |
Correct |
6 ms |
5392 KB |
Output is correct |
22 |
Correct |
3 ms |
5076 KB |
Output is correct |
23 |
Correct |
3 ms |
5076 KB |
Output is correct |
24 |
Correct |
2 ms |
5076 KB |
Output is correct |
25 |
Correct |
3 ms |
5136 KB |
Output is correct |
26 |
Correct |
3 ms |
5204 KB |
Output is correct |
27 |
Correct |
3 ms |
5204 KB |
Output is correct |
28 |
Correct |
3 ms |
5204 KB |
Output is correct |
29 |
Correct |
5 ms |
5268 KB |
Output is correct |
30 |
Correct |
5 ms |
5240 KB |
Output is correct |
31 |
Correct |
3 ms |
5204 KB |
Output is correct |
32 |
Correct |
3 ms |
5204 KB |
Output is correct |
33 |
Correct |
3 ms |
5204 KB |
Output is correct |
34 |
Correct |
4 ms |
5204 KB |
Output is correct |
35 |
Correct |
4 ms |
5204 KB |
Output is correct |
36 |
Correct |
4 ms |
5264 KB |
Output is correct |
37 |
Correct |
3 ms |
5268 KB |
Output is correct |
38 |
Correct |
4 ms |
5332 KB |
Output is correct |
39 |
Correct |
4 ms |
5332 KB |
Output is correct |
40 |
Correct |
6 ms |
5332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5008 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5076 KB |
Output is correct |
5 |
Correct |
3 ms |
5076 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
2 ms |
5076 KB |
Output is correct |
8 |
Correct |
3 ms |
5076 KB |
Output is correct |
9 |
Correct |
3 ms |
5076 KB |
Output is correct |
10 |
Correct |
2 ms |
5004 KB |
Output is correct |
11 |
Correct |
3 ms |
5004 KB |
Output is correct |
12 |
Correct |
2 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
2 ms |
5004 KB |
Output is correct |
16 |
Correct |
3 ms |
5076 KB |
Output is correct |
17 |
Correct |
3 ms |
5076 KB |
Output is correct |
18 |
Correct |
3 ms |
5076 KB |
Output is correct |
19 |
Correct |
3 ms |
5112 KB |
Output is correct |
20 |
Correct |
3 ms |
5076 KB |
Output is correct |
21 |
Correct |
6 ms |
5392 KB |
Output is correct |
22 |
Correct |
3 ms |
5076 KB |
Output is correct |
23 |
Correct |
3 ms |
5076 KB |
Output is correct |
24 |
Correct |
2 ms |
5076 KB |
Output is correct |
25 |
Correct |
3 ms |
5136 KB |
Output is correct |
26 |
Correct |
3 ms |
5204 KB |
Output is correct |
27 |
Correct |
3 ms |
5204 KB |
Output is correct |
28 |
Correct |
3 ms |
5204 KB |
Output is correct |
29 |
Correct |
5 ms |
5268 KB |
Output is correct |
30 |
Correct |
5 ms |
5240 KB |
Output is correct |
31 |
Correct |
3 ms |
5204 KB |
Output is correct |
32 |
Correct |
3 ms |
5204 KB |
Output is correct |
33 |
Correct |
3 ms |
5204 KB |
Output is correct |
34 |
Correct |
4 ms |
5204 KB |
Output is correct |
35 |
Correct |
4 ms |
5204 KB |
Output is correct |
36 |
Correct |
4 ms |
5264 KB |
Output is correct |
37 |
Correct |
3 ms |
5268 KB |
Output is correct |
38 |
Correct |
4 ms |
5332 KB |
Output is correct |
39 |
Correct |
4 ms |
5332 KB |
Output is correct |
40 |
Correct |
6 ms |
5332 KB |
Output is correct |
41 |
Correct |
116 ms |
30636 KB |
Output is correct |
42 |
Correct |
130 ms |
18660 KB |
Output is correct |
43 |
Correct |
108 ms |
18728 KB |
Output is correct |
44 |
Correct |
110 ms |
18696 KB |
Output is correct |
45 |
Correct |
141 ms |
18824 KB |
Output is correct |
46 |
Correct |
327 ms |
31632 KB |
Output is correct |
47 |
Correct |
310 ms |
31800 KB |
Output is correct |
48 |
Correct |
299 ms |
31716 KB |
Output is correct |
49 |
Correct |
301 ms |
31640 KB |
Output is correct |
50 |
Correct |
77 ms |
18896 KB |
Output is correct |
51 |
Correct |
78 ms |
18908 KB |
Output is correct |
52 |
Correct |
75 ms |
18928 KB |
Output is correct |
53 |
Correct |
212 ms |
32536 KB |
Output is correct |
54 |
Correct |
203 ms |
32468 KB |
Output is correct |
55 |
Correct |
201 ms |
32480 KB |
Output is correct |
56 |
Correct |
8 ms |
5460 KB |
Output is correct |
57 |
Correct |
590 ms |
9644 KB |
Output is correct |
58 |
Execution timed out |
1068 ms |
24592 KB |
Time limit exceeded |
59 |
Halted |
0 ms |
0 KB |
- |