#include <bits/stdc++.h>
using namespace std;
// #define int long long
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define reps(i, s, n) for (int i = s; i < (n); ++i)
#define pb push_back
#define sz(a) (int) (a.size())
const int N = 2e5 + 5;
const int inf = 1e9;
vector<int> g[N];
int s[N], mdist[N], used[N], res, d;
vector<pair<int, int>> centroids[N], vs;
void sizes(int v, int p) {
s[v] = 1;
for (auto &u : g[v]) {
if (u != p && !used[u]) {
sizes(u, v);
s[v] += s[u];
}
}
}
int centroid(int v, int p, int n) {
for (auto &u : g[v]) {
if (u != p && !used[u] && s[u] > n / 2) {
return centroid(u, v, n);
}
}
return v;
}
void add_centroid(int v, int p, int centroid, int dist) {
centroids[v].emplace_back(centroid, dist);
for (auto &u : g[v]) {
if (u != p && !used[u]) {
add_centroid(u, v, centroid, dist + 1);
}
}
}
void decomposition1(int v) {
used[v] = 1;
sizes(v, -1);
add_centroid(v, -1, v, 0);
for (auto &u : g[v]) {
if (!used[u]) {
decomposition1(centroid(u, v, s[u]));
}
}
}
void dfs(int v, int p, int dst) {
vs.emplace_back(dst, v);
for (auto &u : g[v]) {
if (u != p) {
dfs(u, v, dst + 1);
}
}
}
void decomposition2(int v) {
used[v] = 1;
sizes(v, -1);
vs.clear();
dfs(v, -1, 0);
sort(vs.begin(), vs.end());
auto can = [&] (int ver, int dst) -> bool {
for (auto &[centroid, dist_to_centroid] : centroids[ver]) {
if (dist_to_centroid + mdist[centroid] < d) {
return false;
}
}
return true;
};
int m = sz(vs), r = m, cnt = 0;
rep(l, m) {
while (r - 1 >= l && vs[r - 1].first >= max(vs[l].first, d - vs[l].first)) {
r--;
int ver = vs[r].second;
int dst = vs[r].first;
if (can(ver, dst)) {
cnt++;
for (auto &[centroid, dist_to_centroid] : centroids[ver]) {
mdist[centroid] = min(mdist[centroid], dist_to_centroid);
}
}
}
if (l == r) {
res = max(res, cnt);
break;
} else {
res = max(res, cnt + can(vs[l].second, vs[l].first));
}
}
for (auto &[vd, ver] : vs) {
for (auto &[centroid, dist_to_centroid] : centroids[ver]) {
mdist[centroid] = inf;
}
}
for (auto &u : g[v]) {
if (!used[u]) {
decomposition2(centroid(u, v, s[u]));
}
}
}
void solve() {
fill(mdist, mdist + N, inf);
int n;
cin >> n >> d;
if (d > n - 1) {
cout << 1;
return;
}
if (d == 0) {
cout << n;
return;
}
reps(i, 1, n) {
int p;
cin >> p;
g[p].push_back(i);
g[i].push_back(p);
}
decomposition1(0);
fill(used, used + N, 0);
decomposition2(0);
cout << res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
11220 KB |
Output is correct |
2 |
Correct |
6 ms |
11220 KB |
Output is correct |
3 |
Correct |
5 ms |
11220 KB |
Output is correct |
4 |
Correct |
6 ms |
11220 KB |
Output is correct |
5 |
Correct |
6 ms |
11220 KB |
Output is correct |
6 |
Correct |
6 ms |
11220 KB |
Output is correct |
7 |
Correct |
6 ms |
11276 KB |
Output is correct |
8 |
Correct |
5 ms |
11220 KB |
Output is correct |
9 |
Correct |
6 ms |
11200 KB |
Output is correct |
10 |
Correct |
6 ms |
11220 KB |
Output is correct |
11 |
Correct |
6 ms |
11220 KB |
Output is correct |
12 |
Correct |
6 ms |
11220 KB |
Output is correct |
13 |
Correct |
6 ms |
11220 KB |
Output is correct |
14 |
Correct |
7 ms |
11220 KB |
Output is correct |
15 |
Correct |
6 ms |
11220 KB |
Output is correct |
16 |
Correct |
7 ms |
11160 KB |
Output is correct |
17 |
Correct |
6 ms |
11168 KB |
Output is correct |
18 |
Correct |
6 ms |
11220 KB |
Output is correct |
19 |
Correct |
8 ms |
11236 KB |
Output is correct |
20 |
Correct |
6 ms |
11220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
11220 KB |
Output is correct |
2 |
Correct |
6 ms |
11220 KB |
Output is correct |
3 |
Correct |
5 ms |
11220 KB |
Output is correct |
4 |
Correct |
6 ms |
11220 KB |
Output is correct |
5 |
Correct |
6 ms |
11220 KB |
Output is correct |
6 |
Correct |
6 ms |
11220 KB |
Output is correct |
7 |
Correct |
6 ms |
11276 KB |
Output is correct |
8 |
Correct |
5 ms |
11220 KB |
Output is correct |
9 |
Correct |
6 ms |
11200 KB |
Output is correct |
10 |
Correct |
6 ms |
11220 KB |
Output is correct |
11 |
Correct |
6 ms |
11220 KB |
Output is correct |
12 |
Correct |
6 ms |
11220 KB |
Output is correct |
13 |
Correct |
6 ms |
11220 KB |
Output is correct |
14 |
Correct |
7 ms |
11220 KB |
Output is correct |
15 |
Correct |
6 ms |
11220 KB |
Output is correct |
16 |
Correct |
7 ms |
11160 KB |
Output is correct |
17 |
Correct |
6 ms |
11168 KB |
Output is correct |
18 |
Correct |
6 ms |
11220 KB |
Output is correct |
19 |
Correct |
8 ms |
11236 KB |
Output is correct |
20 |
Correct |
6 ms |
11220 KB |
Output is correct |
21 |
Correct |
201 ms |
11664 KB |
Output is correct |
22 |
Correct |
36 ms |
11348 KB |
Output is correct |
23 |
Correct |
32 ms |
11348 KB |
Output is correct |
24 |
Correct |
34 ms |
11336 KB |
Output is correct |
25 |
Correct |
134 ms |
11396 KB |
Output is correct |
26 |
Correct |
139 ms |
11404 KB |
Output is correct |
27 |
Correct |
125 ms |
11400 KB |
Output is correct |
28 |
Correct |
254 ms |
11488 KB |
Output is correct |
29 |
Correct |
294 ms |
11500 KB |
Output is correct |
30 |
Correct |
279 ms |
11504 KB |
Output is correct |
31 |
Correct |
277 ms |
11492 KB |
Output is correct |
32 |
Correct |
168 ms |
11488 KB |
Output is correct |
33 |
Correct |
147 ms |
11476 KB |
Output is correct |
34 |
Correct |
154 ms |
11472 KB |
Output is correct |
35 |
Correct |
153 ms |
11472 KB |
Output is correct |
36 |
Correct |
219 ms |
11488 KB |
Output is correct |
37 |
Correct |
195 ms |
11532 KB |
Output is correct |
38 |
Correct |
222 ms |
11560 KB |
Output is correct |
39 |
Correct |
252 ms |
11584 KB |
Output is correct |
40 |
Correct |
240 ms |
11664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
11220 KB |
Output is correct |
2 |
Correct |
6 ms |
11220 KB |
Output is correct |
3 |
Correct |
5 ms |
11220 KB |
Output is correct |
4 |
Correct |
6 ms |
11220 KB |
Output is correct |
5 |
Correct |
6 ms |
11220 KB |
Output is correct |
6 |
Correct |
6 ms |
11220 KB |
Output is correct |
7 |
Correct |
6 ms |
11276 KB |
Output is correct |
8 |
Correct |
5 ms |
11220 KB |
Output is correct |
9 |
Correct |
6 ms |
11200 KB |
Output is correct |
10 |
Correct |
6 ms |
11220 KB |
Output is correct |
11 |
Correct |
6 ms |
11220 KB |
Output is correct |
12 |
Correct |
6 ms |
11220 KB |
Output is correct |
13 |
Correct |
6 ms |
11220 KB |
Output is correct |
14 |
Correct |
7 ms |
11220 KB |
Output is correct |
15 |
Correct |
6 ms |
11220 KB |
Output is correct |
16 |
Correct |
7 ms |
11160 KB |
Output is correct |
17 |
Correct |
6 ms |
11168 KB |
Output is correct |
18 |
Correct |
6 ms |
11220 KB |
Output is correct |
19 |
Correct |
8 ms |
11236 KB |
Output is correct |
20 |
Correct |
6 ms |
11220 KB |
Output is correct |
21 |
Correct |
201 ms |
11664 KB |
Output is correct |
22 |
Correct |
36 ms |
11348 KB |
Output is correct |
23 |
Correct |
32 ms |
11348 KB |
Output is correct |
24 |
Correct |
34 ms |
11336 KB |
Output is correct |
25 |
Correct |
134 ms |
11396 KB |
Output is correct |
26 |
Correct |
139 ms |
11404 KB |
Output is correct |
27 |
Correct |
125 ms |
11400 KB |
Output is correct |
28 |
Correct |
254 ms |
11488 KB |
Output is correct |
29 |
Correct |
294 ms |
11500 KB |
Output is correct |
30 |
Correct |
279 ms |
11504 KB |
Output is correct |
31 |
Correct |
277 ms |
11492 KB |
Output is correct |
32 |
Correct |
168 ms |
11488 KB |
Output is correct |
33 |
Correct |
147 ms |
11476 KB |
Output is correct |
34 |
Correct |
154 ms |
11472 KB |
Output is correct |
35 |
Correct |
153 ms |
11472 KB |
Output is correct |
36 |
Correct |
219 ms |
11488 KB |
Output is correct |
37 |
Correct |
195 ms |
11532 KB |
Output is correct |
38 |
Correct |
222 ms |
11560 KB |
Output is correct |
39 |
Correct |
252 ms |
11584 KB |
Output is correct |
40 |
Correct |
240 ms |
11664 KB |
Output is correct |
41 |
Execution timed out |
1080 ms |
29104 KB |
Time limit exceeded |
42 |
Halted |
0 ms |
0 KB |
- |