#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())
void solve() {
int n, d;
cin >> n >> d;
if (d > n - 1) {
cout << 1;
return;
}
if (d == 0) {
cout << n;
return;
}
vector<vector<int>> g(n);
reps(i, 1, n) {
int p;
cin >> p;
g[p].push_back(i);
g[i].push_back(p);
}
vector<int> s(n), used(n);
function<void(int, int)> 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];
}
}
};
function<int(int, int, 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;
};
vector<vector<pair<int, int>>> centroids(n);
function<void(int, int, int, int)> 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);
}
}
};
function<void(int)> 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]));
}
}
};
decomposition1(0);
int timer = 0;
vector<pair<int, int>> vs;
vector<int> tin(n), tout(n), par(n);
function<void(int, int, int)> dfs = [&] (int v, int p, int dst) {
par[v] = p;
tin[v] = timer++;
vs.emplace_back(dst, v);
for (auto &u : g[v]) {
if (u != p) {
dfs(u, v, dst + 1);
}
}
tout[v] = timer;
};
const int inf = 1e9;
debug(centroids);
int res = 0;
vector<int> mdist(n, inf);
function<void(int)> decomposition2 = [&] (int v) {
used[v] = 1;
sizes(v, -1);
debug(v);
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]));
}
}
};
used.assign(n, 0);
decomposition2(0);
cout << res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Compilation message
catinatree.cpp: In function 'void solve()':
catinatree.cpp:9:20: warning: statement has no effect [-Wunused-value]
9 | #define debug(...) 42
| ^~
catinatree.cpp:100:3: note: in expansion of macro 'debug'
100 | debug(centroids);
| ^~~~~
catinatree.cpp: In lambda function:
catinatree.cpp:9:20: warning: statement has no effect [-Wunused-value]
9 | #define debug(...) 42
| ^~
catinatree.cpp:107:5: note: in expansion of macro 'debug'
107 | debug(v);
| ^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
225 ms |
1108 KB |
Output is correct |
22 |
Correct |
34 ms |
340 KB |
Output is correct |
23 |
Correct |
32 ms |
468 KB |
Output is correct |
24 |
Correct |
30 ms |
340 KB |
Output is correct |
25 |
Correct |
151 ms |
596 KB |
Output is correct |
26 |
Correct |
138 ms |
716 KB |
Output is correct |
27 |
Correct |
131 ms |
628 KB |
Output is correct |
28 |
Correct |
292 ms |
896 KB |
Output is correct |
29 |
Correct |
351 ms |
844 KB |
Output is correct |
30 |
Correct |
298 ms |
724 KB |
Output is correct |
31 |
Correct |
309 ms |
844 KB |
Output is correct |
32 |
Correct |
183 ms |
740 KB |
Output is correct |
33 |
Correct |
165 ms |
724 KB |
Output is correct |
34 |
Correct |
185 ms |
732 KB |
Output is correct |
35 |
Correct |
177 ms |
724 KB |
Output is correct |
36 |
Correct |
209 ms |
724 KB |
Output is correct |
37 |
Correct |
228 ms |
972 KB |
Output is correct |
38 |
Correct |
258 ms |
964 KB |
Output is correct |
39 |
Correct |
258 ms |
992 KB |
Output is correct |
40 |
Correct |
265 ms |
1136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
225 ms |
1108 KB |
Output is correct |
22 |
Correct |
34 ms |
340 KB |
Output is correct |
23 |
Correct |
32 ms |
468 KB |
Output is correct |
24 |
Correct |
30 ms |
340 KB |
Output is correct |
25 |
Correct |
151 ms |
596 KB |
Output is correct |
26 |
Correct |
138 ms |
716 KB |
Output is correct |
27 |
Correct |
131 ms |
628 KB |
Output is correct |
28 |
Correct |
292 ms |
896 KB |
Output is correct |
29 |
Correct |
351 ms |
844 KB |
Output is correct |
30 |
Correct |
298 ms |
724 KB |
Output is correct |
31 |
Correct |
309 ms |
844 KB |
Output is correct |
32 |
Correct |
183 ms |
740 KB |
Output is correct |
33 |
Correct |
165 ms |
724 KB |
Output is correct |
34 |
Correct |
185 ms |
732 KB |
Output is correct |
35 |
Correct |
177 ms |
724 KB |
Output is correct |
36 |
Correct |
209 ms |
724 KB |
Output is correct |
37 |
Correct |
228 ms |
972 KB |
Output is correct |
38 |
Correct |
258 ms |
964 KB |
Output is correct |
39 |
Correct |
258 ms |
992 KB |
Output is correct |
40 |
Correct |
265 ms |
1136 KB |
Output is correct |
41 |
Execution timed out |
1088 ms |
43536 KB |
Time limit exceeded |
42 |
Halted |
0 ms |
0 KB |
- |