#include <iostream>
#include <vector>
#include <bitset>
#include <map>
using namespace std;
const int N=2e5+10;
const int LG=18;
int n,d;
int pw2[LG];
int par[N][LG];
vector<int> ma[N],vep[N];
int part[N];
int h[N],dist[N],sz[N];
bitset<N> dead;
int cn;
void dfs(int&x,int p=0)
{
sz[x]=1;
par[x][0]=p;
for(int j=1;j<LG;j++)
par[x][j]=par[par[x][j-1]][j-1];
for(int&y:ma[x])
{
if(y!=p)
{
dfs(y,x);
sz[x]+=sz[y];
}
}
}
int find_centriod(int&x,int p=0)
{
for(int&y:ma[x])
{
if(y!=p and !dead[y] and sz[y]>(cn/2))
{
sz[x]-=sz[y];
sz[y]+=sz[x];
return find_centriod(y,x);
}
}
return x;
}
int solve(int&x)
{
cn=sz[x];
int c=find_centriod(x);
dead[c]=1;
for(int&y:ma[c])
if(!dead[y])
part[solve(y)]=c;
return c;
}
// map<pair<int,int>,int> memo;
int dist1(int x,int y)
{
if(h[x]<h[y])
swap(x,y);
int ans=0;
for(int j=LG-1;j>=0;j--)
{
if(h[par[x][j]]>=h[y])
{
ans+=pw2[j];
x=par[x][j];
}
}
for(int j=LG-1;j>=0;j--)
{
if(par[x][j]!=par[y][j])
{
x=par[x][j];
y=par[y][j];
ans+=pw2[j];
ans+=pw2[j];
}
}
// cout<<"Distance btw "<<x<<' '<<y<<' ';
// cout<<ans+(x!=y)<<endl;
return ans+(x!=y);
}
void color(int&st)
{
// cout<<"Marked "<<st<<endl;
int x=st;
while(x>0)
{
dist[x]=min(dist[x],dist1(x,st));
x=part[x];
}
}
int query(int&st)
{
int x=st;
int ans=dist[x];
while(x>0)
{
ans=min(ans,dist1(x,st)+dist[x]);
x=part[x];
}
return ans;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
pw2[0]=1;
for(int i=1;i<LG;i++)
pw2[i]=(pw2[i-1]*2);
cin>>n>>d;
h[1]=1;
vep[1].push_back(1);
int max_h=1;
for(int i=2;i<=n;i++)
{
int p;
cin>>p;
p++;
h[i]=h[p]+1;
vep[h[i]].push_back(i);
max_h=max(max_h,h[i]);
ma[p].push_back(i);
ma[i].push_back(p);
}
int ans=0;
for(int j=1;j<=n;j++)
dist[j]=1e9;
int o_1=1;
dfs(o_1);
solve(o_1);
for(int cur_h=max_h;cur_h>=1;cur_h--)
{
for(int&v:vep[cur_h])
{
if(query(v)>=d)
{
ans++;
color(v);
}
}
}
cout<<ans<<'\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14684 KB |
Output is correct |
2 |
Incorrect |
3 ms |
14684 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14684 KB |
Output is correct |
2 |
Incorrect |
3 ms |
14684 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14684 KB |
Output is correct |
2 |
Incorrect |
3 ms |
14684 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |