#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define maxn 400005
#define maxl 25
const int inf=1e9;
int n,d,depth[maxn],Min[maxn][maxl],L[maxn],len,logx[maxn];
int dad[maxn],res[maxn],child[maxn],sz;
bool used[maxn];
vector<int> edge[maxn];
void dfs(int u,int par){
L[u]=++len;Min[len][0]=len;
depth[L[u]]=depth[L[par]]+1;
for(int v:edge[u]){
if(v==par) continue;
dfs(v,u);
Min[++len][0]=L[u];
}
}
void build_sparse(){
for(int i=1;i<=18;i++){
for(int j=1;j<=(len-(1<<i)+1);j++) Min[j][i]=min(Min[j][i-1],Min[j+(1<<(i-1))][i-1]);
}
for(int i=2;i<=len;i++) logx[i]=logx[i/2]+1;
}
void dfs2(int u,int par){
child[u]=1;
for(int v:edge[u]){
if(v==par || used[v]) continue;
dfs2(v,u);child[u]+=child[v];
}
}
int findcen(int u,int par){
for(int v:edge[u]){
if(v==par || used[v]) continue;
if(child[v]>sz/2) return findcen(v,u);
}
return u;
}
void decompose(int u,int par){
dfs2(u,par);sz=child[u];
int cen=findcen(u,par);
dad[cen]=par;used[cen]=true;
for(int v:edge[cen]){
if(v==par || used[v]) continue;
decompose(v,cen);
}
}
int dist(int u,int v){
u=L[u];v=L[v];
if(u>v) swap(u,v);
int p=logx[v-u+1],a=min(Min[u][p],Min[v-(1<<p)+1][p]);
return depth[u]+depth[v]-2*depth[a];
}
void update(int u){
int a=u;
while(a!=0){
res[a]=min(res[a],dist(a,u));
a=dad[a];
}
}
int query(int u){
int r=inf,a=u;
while(a!=0){
r=min(r,dist(u,a)+res[a]);
a=dad[a];
}
return r;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin >> n >> d;
for(int i=2;i<=n;i++){
int p;cin >> p;
edge[p+1].push_back(i);
edge[i].push_back(p+1);
}
dfs(1,0);build_sparse();
decompose(1,0);
vector<pii> p;
for(int i=1;i<=n;i++){
res[i]=inf;
p.push_back({depth[L[i]],i});
}
sort(p.begin(),p.end(),greater<pii>());
int ans=0;
for(auto it:p){
if(query(it.second)>=d){ans++;update(it.second);}
}
cout << ans << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9720 KB |
Output is correct |
4 |
Correct |
5 ms |
9724 KB |
Output is correct |
5 |
Correct |
5 ms |
9724 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9720 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9724 KB |
Output is correct |
10 |
Correct |
5 ms |
9772 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
7 ms |
9740 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
6 ms |
9812 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
7 ms |
9684 KB |
Output is correct |
17 |
Correct |
6 ms |
9684 KB |
Output is correct |
18 |
Correct |
5 ms |
9684 KB |
Output is correct |
19 |
Correct |
6 ms |
9720 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9720 KB |
Output is correct |
4 |
Correct |
5 ms |
9724 KB |
Output is correct |
5 |
Correct |
5 ms |
9724 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9720 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9724 KB |
Output is correct |
10 |
Correct |
5 ms |
9772 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
7 ms |
9740 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
6 ms |
9812 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
7 ms |
9684 KB |
Output is correct |
17 |
Correct |
6 ms |
9684 KB |
Output is correct |
18 |
Correct |
5 ms |
9684 KB |
Output is correct |
19 |
Correct |
6 ms |
9720 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
6 ms |
10196 KB |
Output is correct |
22 |
Correct |
5 ms |
9812 KB |
Output is correct |
23 |
Correct |
5 ms |
9812 KB |
Output is correct |
24 |
Correct |
5 ms |
9812 KB |
Output is correct |
25 |
Correct |
5 ms |
9980 KB |
Output is correct |
26 |
Correct |
6 ms |
9940 KB |
Output is correct |
27 |
Correct |
6 ms |
9940 KB |
Output is correct |
28 |
Correct |
9 ms |
10152 KB |
Output is correct |
29 |
Correct |
8 ms |
10196 KB |
Output is correct |
30 |
Correct |
8 ms |
10196 KB |
Output is correct |
31 |
Correct |
6 ms |
10184 KB |
Output is correct |
32 |
Correct |
7 ms |
10196 KB |
Output is correct |
33 |
Correct |
6 ms |
10108 KB |
Output is correct |
34 |
Correct |
6 ms |
10108 KB |
Output is correct |
35 |
Correct |
6 ms |
10068 KB |
Output is correct |
36 |
Correct |
6 ms |
10196 KB |
Output is correct |
37 |
Correct |
6 ms |
10196 KB |
Output is correct |
38 |
Correct |
6 ms |
10116 KB |
Output is correct |
39 |
Correct |
6 ms |
10196 KB |
Output is correct |
40 |
Correct |
6 ms |
10244 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9720 KB |
Output is correct |
4 |
Correct |
5 ms |
9724 KB |
Output is correct |
5 |
Correct |
5 ms |
9724 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9720 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9724 KB |
Output is correct |
10 |
Correct |
5 ms |
9772 KB |
Output is correct |
11 |
Correct |
5 ms |
9684 KB |
Output is correct |
12 |
Correct |
7 ms |
9740 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
6 ms |
9812 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
7 ms |
9684 KB |
Output is correct |
17 |
Correct |
6 ms |
9684 KB |
Output is correct |
18 |
Correct |
5 ms |
9684 KB |
Output is correct |
19 |
Correct |
6 ms |
9720 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
6 ms |
10196 KB |
Output is correct |
22 |
Correct |
5 ms |
9812 KB |
Output is correct |
23 |
Correct |
5 ms |
9812 KB |
Output is correct |
24 |
Correct |
5 ms |
9812 KB |
Output is correct |
25 |
Correct |
5 ms |
9980 KB |
Output is correct |
26 |
Correct |
6 ms |
9940 KB |
Output is correct |
27 |
Correct |
6 ms |
9940 KB |
Output is correct |
28 |
Correct |
9 ms |
10152 KB |
Output is correct |
29 |
Correct |
8 ms |
10196 KB |
Output is correct |
30 |
Correct |
8 ms |
10196 KB |
Output is correct |
31 |
Correct |
6 ms |
10184 KB |
Output is correct |
32 |
Correct |
7 ms |
10196 KB |
Output is correct |
33 |
Correct |
6 ms |
10108 KB |
Output is correct |
34 |
Correct |
6 ms |
10108 KB |
Output is correct |
35 |
Correct |
6 ms |
10068 KB |
Output is correct |
36 |
Correct |
6 ms |
10196 KB |
Output is correct |
37 |
Correct |
6 ms |
10196 KB |
Output is correct |
38 |
Correct |
6 ms |
10116 KB |
Output is correct |
39 |
Correct |
6 ms |
10196 KB |
Output is correct |
40 |
Correct |
6 ms |
10244 KB |
Output is correct |
41 |
Correct |
166 ms |
61952 KB |
Output is correct |
42 |
Correct |
144 ms |
37324 KB |
Output is correct |
43 |
Correct |
166 ms |
37332 KB |
Output is correct |
44 |
Correct |
139 ms |
37308 KB |
Output is correct |
45 |
Correct |
154 ms |
37324 KB |
Output is correct |
46 |
Correct |
366 ms |
64976 KB |
Output is correct |
47 |
Correct |
359 ms |
64812 KB |
Output is correct |
48 |
Correct |
347 ms |
64852 KB |
Output is correct |
49 |
Correct |
350 ms |
64836 KB |
Output is correct |
50 |
Correct |
104 ms |
37596 KB |
Output is correct |
51 |
Correct |
138 ms |
37524 KB |
Output is correct |
52 |
Correct |
119 ms |
37596 KB |
Output is correct |
53 |
Correct |
225 ms |
65216 KB |
Output is correct |
54 |
Correct |
228 ms |
65264 KB |
Output is correct |
55 |
Correct |
244 ms |
65344 KB |
Output is correct |
56 |
Correct |
7 ms |
10496 KB |
Output is correct |
57 |
Correct |
20 ms |
17236 KB |
Output is correct |
58 |
Correct |
103 ms |
44252 KB |
Output is correct |
59 |
Correct |
302 ms |
72560 KB |
Output is correct |
60 |
Correct |
173 ms |
63552 KB |
Output is correct |
61 |
Correct |
242 ms |
62096 KB |
Output is correct |