#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, d;
ll arr[200002];
vector<int> link[200002];
int sz[200002];
bool centroidUsed[200002];
int centroidPar[200002];
vector<int> centroidChild[200002];
int depth[200002];
int par[200002];
int LCADB[200002][22], radius[200002];
void setSize(int x, int par = -1){
sz[x] = 1;
for(auto y: link[x]){
if(y == par || centroidUsed[y]) continue;
setSize(y, x);
sz[x] += sz[y];
}
}
void dfs(int x, int p = -1){
for(auto y: link[x]){
if(y == p) continue;
depth[y] = depth[x] + 1;
LCADB[y][0] = par[y] = x;
dfs(y, x);
}
}
int getLCA(int x, int y){
if(depth[x] < depth[y]) swap(x, y);
for(int i=0; i<20; i++) if((depth[x] - depth[y]) & (1<<i)) x = LCADB[x][i];
if(x==y) return x;
for(int i=19; i>=0; i--) if(LCADB[x][i] != LCADB[y][i]) x = LCADB[x][i], y = LCADB[y][i];
return par[x];
}
int dist(int x, int y){
return depth[x] + depth[y] - depth[getLCA(x, y)] * 2;
}
int findCentroid(int x, int s, int par = -1){
for(auto y: link[x]){
if(y == par || centroidUsed[y]) continue;
if(sz[y] > s/2) return findCentroid(y, s, x);
}
return x;
}
int centroidDecomposition(int x){
setSize(x);
int c = findCentroid(x, sz[x]);
centroidUsed[c] = 1;
for(auto y: link[c]){
if(centroidUsed[y]) continue;
int node = centroidDecomposition(y);
centroidPar[node] = c;
centroidChild[c].push_back(node);
}
return c;
}
bool alreadyUsed(int x){
int root = x;
while(root){
if(dist(root, x) <= radius[root]) return true;
root = centroidPar[root];
}
return false;
}
void mark(int x){
int root = x;
while(root){
radius[root] = max(radius[root], d - dist(root, x) - 1);
root = centroidPar[root];
}
}
int ans;
int main(){
scanf("%d %d", &n, &d);
for(int i=1; i<n; i++){
int x, y;
scanf("%d", &x);
y=i+1, x++;
link[x].push_back(y);
link[y].push_back(x);
}
for(int i=1; i<=n; i++) radius[i] = -1;
dfs(1);
centroidDecomposition(1);
for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
vector<pair<int, int> > vec;
for(int i=1; i<=n; i++) vec.push_back(make_pair(depth[i], i));
sort(vec.rbegin(), vec.rend());
for(pair<int, int> p: vec){
int x = p.second;
if(alreadyUsed(x)) continue;
ans++;
mark(x);
}
printf("%d", ans);
}
Compilation message
catinatree.cpp: In function 'int main()':
catinatree.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d %d", &n, &d);
| ~~~~~^~~~~~~~~~~~~~~~~
catinatree.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9688 KB |
Output is correct |
3 |
Correct |
6 ms |
9676 KB |
Output is correct |
4 |
Correct |
7 ms |
9704 KB |
Output is correct |
5 |
Correct |
7 ms |
9708 KB |
Output is correct |
6 |
Correct |
5 ms |
9676 KB |
Output is correct |
7 |
Correct |
5 ms |
9680 KB |
Output is correct |
8 |
Correct |
5 ms |
9676 KB |
Output is correct |
9 |
Correct |
6 ms |
9676 KB |
Output is correct |
10 |
Correct |
5 ms |
9708 KB |
Output is correct |
11 |
Correct |
5 ms |
9676 KB |
Output is correct |
12 |
Correct |
7 ms |
9696 KB |
Output is correct |
13 |
Correct |
5 ms |
9676 KB |
Output is correct |
14 |
Correct |
8 ms |
9800 KB |
Output is correct |
15 |
Correct |
6 ms |
9676 KB |
Output is correct |
16 |
Correct |
5 ms |
9640 KB |
Output is correct |
17 |
Correct |
5 ms |
9676 KB |
Output is correct |
18 |
Correct |
6 ms |
9676 KB |
Output is correct |
19 |
Correct |
7 ms |
9676 KB |
Output is correct |
20 |
Correct |
7 ms |
9708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9688 KB |
Output is correct |
3 |
Correct |
6 ms |
9676 KB |
Output is correct |
4 |
Correct |
7 ms |
9704 KB |
Output is correct |
5 |
Correct |
7 ms |
9708 KB |
Output is correct |
6 |
Correct |
5 ms |
9676 KB |
Output is correct |
7 |
Correct |
5 ms |
9680 KB |
Output is correct |
8 |
Correct |
5 ms |
9676 KB |
Output is correct |
9 |
Correct |
6 ms |
9676 KB |
Output is correct |
10 |
Correct |
5 ms |
9708 KB |
Output is correct |
11 |
Correct |
5 ms |
9676 KB |
Output is correct |
12 |
Correct |
7 ms |
9696 KB |
Output is correct |
13 |
Correct |
5 ms |
9676 KB |
Output is correct |
14 |
Correct |
8 ms |
9800 KB |
Output is correct |
15 |
Correct |
6 ms |
9676 KB |
Output is correct |
16 |
Correct |
5 ms |
9640 KB |
Output is correct |
17 |
Correct |
5 ms |
9676 KB |
Output is correct |
18 |
Correct |
6 ms |
9676 KB |
Output is correct |
19 |
Correct |
7 ms |
9676 KB |
Output is correct |
20 |
Correct |
7 ms |
9708 KB |
Output is correct |
21 |
Correct |
7 ms |
10092 KB |
Output is correct |
22 |
Correct |
7 ms |
9712 KB |
Output is correct |
23 |
Correct |
5 ms |
9804 KB |
Output is correct |
24 |
Correct |
5 ms |
9708 KB |
Output is correct |
25 |
Correct |
7 ms |
9836 KB |
Output is correct |
26 |
Correct |
6 ms |
9796 KB |
Output is correct |
27 |
Correct |
6 ms |
9804 KB |
Output is correct |
28 |
Correct |
7 ms |
9932 KB |
Output is correct |
29 |
Correct |
6 ms |
9968 KB |
Output is correct |
30 |
Correct |
6 ms |
9932 KB |
Output is correct |
31 |
Correct |
6 ms |
9972 KB |
Output is correct |
32 |
Correct |
9 ms |
9904 KB |
Output is correct |
33 |
Correct |
6 ms |
9932 KB |
Output is correct |
34 |
Correct |
9 ms |
9932 KB |
Output is correct |
35 |
Correct |
7 ms |
9932 KB |
Output is correct |
36 |
Correct |
6 ms |
9932 KB |
Output is correct |
37 |
Correct |
6 ms |
9968 KB |
Output is correct |
38 |
Correct |
6 ms |
9932 KB |
Output is correct |
39 |
Correct |
7 ms |
9932 KB |
Output is correct |
40 |
Correct |
6 ms |
10060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9688 KB |
Output is correct |
3 |
Correct |
6 ms |
9676 KB |
Output is correct |
4 |
Correct |
7 ms |
9704 KB |
Output is correct |
5 |
Correct |
7 ms |
9708 KB |
Output is correct |
6 |
Correct |
5 ms |
9676 KB |
Output is correct |
7 |
Correct |
5 ms |
9680 KB |
Output is correct |
8 |
Correct |
5 ms |
9676 KB |
Output is correct |
9 |
Correct |
6 ms |
9676 KB |
Output is correct |
10 |
Correct |
5 ms |
9708 KB |
Output is correct |
11 |
Correct |
5 ms |
9676 KB |
Output is correct |
12 |
Correct |
7 ms |
9696 KB |
Output is correct |
13 |
Correct |
5 ms |
9676 KB |
Output is correct |
14 |
Correct |
8 ms |
9800 KB |
Output is correct |
15 |
Correct |
6 ms |
9676 KB |
Output is correct |
16 |
Correct |
5 ms |
9640 KB |
Output is correct |
17 |
Correct |
5 ms |
9676 KB |
Output is correct |
18 |
Correct |
6 ms |
9676 KB |
Output is correct |
19 |
Correct |
7 ms |
9676 KB |
Output is correct |
20 |
Correct |
7 ms |
9708 KB |
Output is correct |
21 |
Correct |
7 ms |
10092 KB |
Output is correct |
22 |
Correct |
7 ms |
9712 KB |
Output is correct |
23 |
Correct |
5 ms |
9804 KB |
Output is correct |
24 |
Correct |
5 ms |
9708 KB |
Output is correct |
25 |
Correct |
7 ms |
9836 KB |
Output is correct |
26 |
Correct |
6 ms |
9796 KB |
Output is correct |
27 |
Correct |
6 ms |
9804 KB |
Output is correct |
28 |
Correct |
7 ms |
9932 KB |
Output is correct |
29 |
Correct |
6 ms |
9968 KB |
Output is correct |
30 |
Correct |
6 ms |
9932 KB |
Output is correct |
31 |
Correct |
6 ms |
9972 KB |
Output is correct |
32 |
Correct |
9 ms |
9904 KB |
Output is correct |
33 |
Correct |
6 ms |
9932 KB |
Output is correct |
34 |
Correct |
9 ms |
9932 KB |
Output is correct |
35 |
Correct |
7 ms |
9932 KB |
Output is correct |
36 |
Correct |
6 ms |
9932 KB |
Output is correct |
37 |
Correct |
6 ms |
9968 KB |
Output is correct |
38 |
Correct |
6 ms |
9932 KB |
Output is correct |
39 |
Correct |
7 ms |
9932 KB |
Output is correct |
40 |
Correct |
6 ms |
10060 KB |
Output is correct |
41 |
Correct |
158 ms |
41884 KB |
Output is correct |
42 |
Correct |
237 ms |
26688 KB |
Output is correct |
43 |
Correct |
131 ms |
26684 KB |
Output is correct |
44 |
Correct |
163 ms |
26796 KB |
Output is correct |
45 |
Correct |
202 ms |
26712 KB |
Output is correct |
46 |
Correct |
419 ms |
43536 KB |
Output is correct |
47 |
Correct |
440 ms |
43656 KB |
Output is correct |
48 |
Correct |
475 ms |
43576 KB |
Output is correct |
49 |
Correct |
428 ms |
43668 KB |
Output is correct |
50 |
Correct |
107 ms |
26052 KB |
Output is correct |
51 |
Correct |
99 ms |
26112 KB |
Output is correct |
52 |
Correct |
88 ms |
26104 KB |
Output is correct |
53 |
Correct |
211 ms |
42292 KB |
Output is correct |
54 |
Correct |
215 ms |
42260 KB |
Output is correct |
55 |
Correct |
209 ms |
42296 KB |
Output is correct |
56 |
Correct |
7 ms |
10188 KB |
Output is correct |
57 |
Correct |
31 ms |
15016 KB |
Output is correct |
58 |
Correct |
176 ms |
34104 KB |
Output is correct |
59 |
Correct |
437 ms |
51076 KB |
Output is correct |
60 |
Correct |
176 ms |
43028 KB |
Output is correct |
61 |
Correct |
262 ms |
42016 KB |
Output is correct |