#include <bits/stdc++.h>
using namespace std;
#define file ""
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 2e5 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;
template<class X, class Y> bool mini(X &a, Y b) {
return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
int n, d;
vector<int> adj[N];
namespace task_n2 {
int dis[5005], chosen[5005];
int v[5005];
void dfs(int u) {
for (int v : adj[u]) if (dis[v] == -1 && !chosen[v]) {
dis[v] = dis[u] + 1;
dfs(v);
}
}
void solve() {
memset(dis, -1, sizeof dis);
dis[1] = 1;
dfs(1);
int cur = 1;
for (int i = 1; i <= n; ++i) if (dis[i] > dis[cur]) cur = i;
chosen[cur] = true;
int ans = 0;
memset(v, 0x3f, sizeof v);
while (true) {
++ans;
memset(dis, -1, sizeof dis);
dis[cur] = 0;
dfs(cur);
for (int i = 1; i <= n; ++i) mini(v[i], dis[i]);
int nxt = -1;
for (int i = 1; i <= n; ++i) if (v[i] >= d) {
if (nxt == -1) nxt = i;
else if (dis[i] > dis[nxt]) nxt = i;
}
if (nxt == -1) break;
cur = nxt;
chosen[cur] = true;
}
cout << ans;
}
}
namespace greedy {
int h[N], f[N];
void dfs(int u, int p) {
h[u] = oo;
for (int v : adj[u]) if (v != p) {
dfs(v, u);
if (h[u] + h[v] + 1 >= d) {
f[u] += f[v];
mini(h[u], h[v] + 1);
}
else {
f[u] += f[v] - 1;
maxi(h[u], h[v] + 1);
}
}
if (h[u] >= d) {
f[u] += 1;
h[u] = 0;
}
}
void solve() {
dfs(1, 0);
cout << f[1];
}
}
namespace sack {
int h[N];
multiset<int> f[N];
void pre_dfs(int u, int p) {
for (int v : adj[u]) if (v != p) {
h[v] = h[u] + 1;
pre_dfs(v, u);
}
}
void sack(int u, int p) {
f[u].insert(h[u]);
for (int v : adj[u]) if (v != p) {
sack(v, u);
if (f[u].size() < f[u].size()) swap(f[u], f[v]);
while (f[u].size() && f[v].size() && *f[u].begin() + *f[v].begin() - 2 * h[u] < d) {
if (*f[u].begin() > *f[v].begin()) f[v].erase(f[v].begin());
else f[u].erase(f[u].begin());
}
for (int x : f[v]) f[u].insert(x);
}
}
void solve() {
pre_dfs(1, 0);
sack(1, 0);
cout << (int) f[1].size();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> n >> d;
for (int i = 2; i <= n; ++i) {
int p;
cin >> p;
++p;
adj[i].push_back(p);
adj[p].push_back(i);
}
// greedy::solve();
// task_n2::solve();
sack::solve();
return 0;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16732 KB |
Output is correct |
2 |
Correct |
3 ms |
16728 KB |
Output is correct |
3 |
Correct |
4 ms |
16732 KB |
Output is correct |
4 |
Correct |
4 ms |
16956 KB |
Output is correct |
5 |
Correct |
3 ms |
16732 KB |
Output is correct |
6 |
Correct |
4 ms |
16732 KB |
Output is correct |
7 |
Correct |
4 ms |
16956 KB |
Output is correct |
8 |
Correct |
4 ms |
16916 KB |
Output is correct |
9 |
Correct |
4 ms |
16732 KB |
Output is correct |
10 |
Correct |
3 ms |
16732 KB |
Output is correct |
11 |
Correct |
4 ms |
16732 KB |
Output is correct |
12 |
Correct |
4 ms |
16732 KB |
Output is correct |
13 |
Correct |
4 ms |
16984 KB |
Output is correct |
14 |
Correct |
4 ms |
16732 KB |
Output is correct |
15 |
Correct |
4 ms |
16732 KB |
Output is correct |
16 |
Correct |
4 ms |
16824 KB |
Output is correct |
17 |
Correct |
4 ms |
16732 KB |
Output is correct |
18 |
Correct |
4 ms |
16732 KB |
Output is correct |
19 |
Correct |
3 ms |
16732 KB |
Output is correct |
20 |
Correct |
4 ms |
16952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16732 KB |
Output is correct |
2 |
Correct |
3 ms |
16728 KB |
Output is correct |
3 |
Correct |
4 ms |
16732 KB |
Output is correct |
4 |
Correct |
4 ms |
16956 KB |
Output is correct |
5 |
Correct |
3 ms |
16732 KB |
Output is correct |
6 |
Correct |
4 ms |
16732 KB |
Output is correct |
7 |
Correct |
4 ms |
16956 KB |
Output is correct |
8 |
Correct |
4 ms |
16916 KB |
Output is correct |
9 |
Correct |
4 ms |
16732 KB |
Output is correct |
10 |
Correct |
3 ms |
16732 KB |
Output is correct |
11 |
Correct |
4 ms |
16732 KB |
Output is correct |
12 |
Correct |
4 ms |
16732 KB |
Output is correct |
13 |
Correct |
4 ms |
16984 KB |
Output is correct |
14 |
Correct |
4 ms |
16732 KB |
Output is correct |
15 |
Correct |
4 ms |
16732 KB |
Output is correct |
16 |
Correct |
4 ms |
16824 KB |
Output is correct |
17 |
Correct |
4 ms |
16732 KB |
Output is correct |
18 |
Correct |
4 ms |
16732 KB |
Output is correct |
19 |
Correct |
3 ms |
16732 KB |
Output is correct |
20 |
Correct |
4 ms |
16952 KB |
Output is correct |
21 |
Correct |
4 ms |
17244 KB |
Output is correct |
22 |
Correct |
4 ms |
16988 KB |
Output is correct |
23 |
Correct |
4 ms |
16848 KB |
Output is correct |
24 |
Correct |
4 ms |
16984 KB |
Output is correct |
25 |
Correct |
4 ms |
17224 KB |
Output is correct |
26 |
Correct |
4 ms |
16988 KB |
Output is correct |
27 |
Correct |
4 ms |
16988 KB |
Output is correct |
28 |
Correct |
4 ms |
16964 KB |
Output is correct |
29 |
Correct |
4 ms |
16984 KB |
Output is correct |
30 |
Correct |
4 ms |
16988 KB |
Output is correct |
31 |
Correct |
4 ms |
16988 KB |
Output is correct |
32 |
Correct |
4 ms |
16988 KB |
Output is correct |
33 |
Correct |
4 ms |
16956 KB |
Output is correct |
34 |
Correct |
4 ms |
16952 KB |
Output is correct |
35 |
Correct |
4 ms |
16988 KB |
Output is correct |
36 |
Correct |
4 ms |
16828 KB |
Output is correct |
37 |
Correct |
4 ms |
16988 KB |
Output is correct |
38 |
Correct |
4 ms |
16988 KB |
Output is correct |
39 |
Correct |
4 ms |
17076 KB |
Output is correct |
40 |
Correct |
25 ms |
27784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16732 KB |
Output is correct |
2 |
Correct |
3 ms |
16728 KB |
Output is correct |
3 |
Correct |
4 ms |
16732 KB |
Output is correct |
4 |
Correct |
4 ms |
16956 KB |
Output is correct |
5 |
Correct |
3 ms |
16732 KB |
Output is correct |
6 |
Correct |
4 ms |
16732 KB |
Output is correct |
7 |
Correct |
4 ms |
16956 KB |
Output is correct |
8 |
Correct |
4 ms |
16916 KB |
Output is correct |
9 |
Correct |
4 ms |
16732 KB |
Output is correct |
10 |
Correct |
3 ms |
16732 KB |
Output is correct |
11 |
Correct |
4 ms |
16732 KB |
Output is correct |
12 |
Correct |
4 ms |
16732 KB |
Output is correct |
13 |
Correct |
4 ms |
16984 KB |
Output is correct |
14 |
Correct |
4 ms |
16732 KB |
Output is correct |
15 |
Correct |
4 ms |
16732 KB |
Output is correct |
16 |
Correct |
4 ms |
16824 KB |
Output is correct |
17 |
Correct |
4 ms |
16732 KB |
Output is correct |
18 |
Correct |
4 ms |
16732 KB |
Output is correct |
19 |
Correct |
3 ms |
16732 KB |
Output is correct |
20 |
Correct |
4 ms |
16952 KB |
Output is correct |
21 |
Correct |
4 ms |
17244 KB |
Output is correct |
22 |
Correct |
4 ms |
16988 KB |
Output is correct |
23 |
Correct |
4 ms |
16848 KB |
Output is correct |
24 |
Correct |
4 ms |
16984 KB |
Output is correct |
25 |
Correct |
4 ms |
17224 KB |
Output is correct |
26 |
Correct |
4 ms |
16988 KB |
Output is correct |
27 |
Correct |
4 ms |
16988 KB |
Output is correct |
28 |
Correct |
4 ms |
16964 KB |
Output is correct |
29 |
Correct |
4 ms |
16984 KB |
Output is correct |
30 |
Correct |
4 ms |
16988 KB |
Output is correct |
31 |
Correct |
4 ms |
16988 KB |
Output is correct |
32 |
Correct |
4 ms |
16988 KB |
Output is correct |
33 |
Correct |
4 ms |
16956 KB |
Output is correct |
34 |
Correct |
4 ms |
16952 KB |
Output is correct |
35 |
Correct |
4 ms |
16988 KB |
Output is correct |
36 |
Correct |
4 ms |
16828 KB |
Output is correct |
37 |
Correct |
4 ms |
16988 KB |
Output is correct |
38 |
Correct |
4 ms |
16988 KB |
Output is correct |
39 |
Correct |
4 ms |
17076 KB |
Output is correct |
40 |
Correct |
25 ms |
27784 KB |
Output is correct |
41 |
Correct |
61 ms |
34764 KB |
Output is correct |
42 |
Correct |
198 ms |
79700 KB |
Output is correct |
43 |
Correct |
38 ms |
24036 KB |
Output is correct |
44 |
Correct |
40 ms |
23888 KB |
Output is correct |
45 |
Correct |
35 ms |
23888 KB |
Output is correct |
46 |
Correct |
280 ms |
93580 KB |
Output is correct |
47 |
Correct |
118 ms |
30912 KB |
Output is correct |
48 |
Correct |
92 ms |
30896 KB |
Output is correct |
49 |
Correct |
110 ms |
30720 KB |
Output is correct |
50 |
Correct |
31 ms |
25904 KB |
Output is correct |
51 |
Correct |
27 ms |
23380 KB |
Output is correct |
52 |
Correct |
26 ms |
23124 KB |
Output is correct |
53 |
Correct |
80 ms |
30636 KB |
Output is correct |
54 |
Correct |
73 ms |
29504 KB |
Output is correct |
55 |
Correct |
72 ms |
29524 KB |
Output is correct |
56 |
Correct |
25 ms |
27228 KB |
Output is correct |
57 |
Correct |
15 ms |
24924 KB |
Output is correct |
58 |
Correct |
55 ms |
51616 KB |
Output is correct |
59 |
Correct |
106 ms |
61152 KB |
Output is correct |
60 |
Correct |
60 ms |
34512 KB |
Output is correct |
61 |
Correct |
60 ms |
30204 KB |
Output is correct |