#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
/*const int MOD = (int) 1e9 + 7;
inline int lgput(int a, int b) {
int ans = 1;
while(b > 0) {
if(b & 1) ans = (1LL * ans * a) % MOD;
b >>= 1;
a = (1LL * a * a) % MOD;
}
return ans;
}
inline void mod(int &x) {
if(x >= MOD)
x -= MOD;
}
inline void add(int &x, int y) {
x += y;
mod(x);
}
inline void sub(int &x, int y) {
x += MOD - y;
mod(x);
}
inline void mul(int &x, int y) {
x = (1LL * x * y) % MOD;
}*/
/*int fact[], invfact[];
inline void prec(int n) {
fact[0] = 1;
for(int i = 1; i <= n; i++) {
fact[i] = (1LL * fact[i - 1] * i) % MOD;
}
invfact[n] = lgput(fact[n], MOD - 2);
for(int i = n - 1; i >= 0; i--) {
invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
}
}
inline int comb(int n, int k) {
if(n < k) return 0;
return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/
using namespace std;
const int MAXN = (int) 2e5;
vector <int> g[MAXN + 1];
int lvl[MAXN + 1], first[MAXN + 1];
vector < pair <int, int> > nodes;
int rmq[20][2 * MAXN + 1], sze;
void dfs(int nod) {
rmq[0][++sze] = nod;
first[nod] = sze;
for(auto it : g[nod]) {
if(lvl[it] == 0) {
lvl[it] = lvl[nod] + 1;
dfs(it);
rmq[0][++sze] = nod;
}
}
nodes.push_back({-lvl[nod], nod});
}
int lg[2 * MAXN + 1];
inline int get_lca(int x, int y) {
x = first[x], y = first[y];
if(x > y) {
swap(x, y);
}
int bit = lg[y - x + 1], a = rmq[bit][x], b = rmq[bit][y - (1 << bit) + 1];
return (lvl[a] < lvl[b] ? a : b);
}
inline int get_dist(int x, int y) {
return lvl[x] + lvl[y] - 2 * lvl[get_lca(x, y)];
}
int sz[MAXN + 1], father[MAXN + 1];
bool mark[MAXN + 1];
void dfs_sz(int nod, int par) {
sz[nod] = 1;
for(auto it : g[nod]) {
if(it != par && mark[it] == 0) {
dfs_sz(it, nod);
sz[nod] += sz[it];
}
}
}
int getCentroid(int nod, int par, int num) {
for(auto it : g[nod]) {
if(it != par && mark[it] == 0 && sz[it] > num / 2) {
return getCentroid(it, nod, num);
}
}
return nod;
}
void make_ct(int nod, int par) {
dfs_sz(nod, par);
int cen = getCentroid(nod, par, sz[nod]);
father[cen] = par;
mark[cen] = 1;
for(auto it : g[cen]) {
if(mark[it] == 0) {
make_ct(it, cen);
}
}
}
int dst[MAXN + 1];
inline void update(int nod) {
int anc = nod;
while(anc > 0) {
dst[anc] = min(dst[anc], get_dist(nod, anc));
anc = father[anc];
}
}
inline int query(int nod) {
int anc = nod, ans = MAXN;
while(anc > 0) {
ans = min(ans, get_dist(nod, anc) + dst[anc]);
anc = father[anc];
}
return ans;
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n, d;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> d;
d = min(d, n);
for(i = 2; i <= n; i++) {
int par;
cin >> par;
g[par + 1].push_back(i);
g[i].push_back(par + 1);
}
dfs(1);
for(i = 2; i <= sze; i++) {
lg[i] = lg[i >> 1] + 1;
}
for(int bit = 1; (1 << bit) <= sze; bit++) {
for(i = 1; i + (1 << bit) <= sze + 1; i++) {
int a = rmq[bit - 1][i], b = rmq[bit - 1][i + (1 << (bit - 1))];
rmq[bit][i] = (lvl[a] < lvl[b] ? a : b);
}
}
make_ct(1, 0);
sort(nodes.begin(), nodes.end());
fill(dst, dst + n + 1, MAXN + 1);
int ans = 0;
for(auto it : nodes) {
if(query(it.second) >= d) {
update(it.second);
ans++;
}
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
6 ms |
5112 KB |
Output is correct |
5 |
Correct |
6 ms |
5112 KB |
Output is correct |
6 |
Correct |
6 ms |
5112 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
7 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
7 ms |
5112 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5112 KB |
Output is correct |
14 |
Correct |
6 ms |
5112 KB |
Output is correct |
15 |
Correct |
7 ms |
5112 KB |
Output is correct |
16 |
Correct |
6 ms |
5112 KB |
Output is correct |
17 |
Correct |
7 ms |
5112 KB |
Output is correct |
18 |
Correct |
6 ms |
5032 KB |
Output is correct |
19 |
Correct |
6 ms |
5084 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
6 ms |
5112 KB |
Output is correct |
5 |
Correct |
6 ms |
5112 KB |
Output is correct |
6 |
Correct |
6 ms |
5112 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
7 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
7 ms |
5112 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5112 KB |
Output is correct |
14 |
Correct |
6 ms |
5112 KB |
Output is correct |
15 |
Correct |
7 ms |
5112 KB |
Output is correct |
16 |
Correct |
6 ms |
5112 KB |
Output is correct |
17 |
Correct |
7 ms |
5112 KB |
Output is correct |
18 |
Correct |
6 ms |
5032 KB |
Output is correct |
19 |
Correct |
6 ms |
5084 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
7 ms |
5496 KB |
Output is correct |
22 |
Correct |
6 ms |
5240 KB |
Output is correct |
23 |
Correct |
6 ms |
5240 KB |
Output is correct |
24 |
Correct |
8 ms |
5240 KB |
Output is correct |
25 |
Correct |
7 ms |
5240 KB |
Output is correct |
26 |
Correct |
7 ms |
5372 KB |
Output is correct |
27 |
Correct |
8 ms |
5240 KB |
Output is correct |
28 |
Correct |
7 ms |
5368 KB |
Output is correct |
29 |
Correct |
7 ms |
5368 KB |
Output is correct |
30 |
Correct |
7 ms |
5368 KB |
Output is correct |
31 |
Correct |
7 ms |
5348 KB |
Output is correct |
32 |
Correct |
8 ms |
5380 KB |
Output is correct |
33 |
Correct |
7 ms |
5368 KB |
Output is correct |
34 |
Correct |
7 ms |
5368 KB |
Output is correct |
35 |
Correct |
8 ms |
5380 KB |
Output is correct |
36 |
Correct |
26 ms |
5496 KB |
Output is correct |
37 |
Correct |
7 ms |
5368 KB |
Output is correct |
38 |
Correct |
7 ms |
5496 KB |
Output is correct |
39 |
Correct |
7 ms |
5368 KB |
Output is correct |
40 |
Correct |
7 ms |
5496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
6 ms |
5112 KB |
Output is correct |
5 |
Correct |
6 ms |
5112 KB |
Output is correct |
6 |
Correct |
6 ms |
5112 KB |
Output is correct |
7 |
Correct |
6 ms |
5112 KB |
Output is correct |
8 |
Correct |
7 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
7 ms |
5112 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5112 KB |
Output is correct |
14 |
Correct |
6 ms |
5112 KB |
Output is correct |
15 |
Correct |
7 ms |
5112 KB |
Output is correct |
16 |
Correct |
6 ms |
5112 KB |
Output is correct |
17 |
Correct |
7 ms |
5112 KB |
Output is correct |
18 |
Correct |
6 ms |
5032 KB |
Output is correct |
19 |
Correct |
6 ms |
5084 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
7 ms |
5496 KB |
Output is correct |
22 |
Correct |
6 ms |
5240 KB |
Output is correct |
23 |
Correct |
6 ms |
5240 KB |
Output is correct |
24 |
Correct |
8 ms |
5240 KB |
Output is correct |
25 |
Correct |
7 ms |
5240 KB |
Output is correct |
26 |
Correct |
7 ms |
5372 KB |
Output is correct |
27 |
Correct |
8 ms |
5240 KB |
Output is correct |
28 |
Correct |
7 ms |
5368 KB |
Output is correct |
29 |
Correct |
7 ms |
5368 KB |
Output is correct |
30 |
Correct |
7 ms |
5368 KB |
Output is correct |
31 |
Correct |
7 ms |
5348 KB |
Output is correct |
32 |
Correct |
8 ms |
5380 KB |
Output is correct |
33 |
Correct |
7 ms |
5368 KB |
Output is correct |
34 |
Correct |
7 ms |
5368 KB |
Output is correct |
35 |
Correct |
8 ms |
5380 KB |
Output is correct |
36 |
Correct |
26 ms |
5496 KB |
Output is correct |
37 |
Correct |
7 ms |
5368 KB |
Output is correct |
38 |
Correct |
7 ms |
5496 KB |
Output is correct |
39 |
Correct |
7 ms |
5368 KB |
Output is correct |
40 |
Correct |
7 ms |
5496 KB |
Output is correct |
41 |
Correct |
154 ms |
45672 KB |
Output is correct |
42 |
Correct |
168 ms |
25836 KB |
Output is correct |
43 |
Correct |
145 ms |
25832 KB |
Output is correct |
44 |
Correct |
174 ms |
25832 KB |
Output is correct |
45 |
Correct |
141 ms |
25884 KB |
Output is correct |
46 |
Correct |
371 ms |
47720 KB |
Output is correct |
47 |
Correct |
369 ms |
47884 KB |
Output is correct |
48 |
Correct |
372 ms |
47868 KB |
Output is correct |
49 |
Correct |
372 ms |
47848 KB |
Output is correct |
50 |
Correct |
88 ms |
25960 KB |
Output is correct |
51 |
Correct |
99 ms |
25964 KB |
Output is correct |
52 |
Correct |
85 ms |
25964 KB |
Output is correct |
53 |
Correct |
192 ms |
48180 KB |
Output is correct |
54 |
Correct |
188 ms |
48228 KB |
Output is correct |
55 |
Correct |
213 ms |
48228 KB |
Output is correct |
56 |
Correct |
8 ms |
5608 KB |
Output is correct |
57 |
Correct |
24 ms |
10488 KB |
Output is correct |
58 |
Correct |
110 ms |
31336 KB |
Output is correct |
59 |
Correct |
299 ms |
53988 KB |
Output is correct |
60 |
Correct |
176 ms |
46756 KB |
Output is correct |
61 |
Correct |
214 ms |
45468 KB |
Output is correct |