一直有三个点tle
做法应该对
就是每次枚举还能选的深度最大的点,用这个点删除其他点
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2e5+10;
int n,d;
int ans;
int depth[maxn];
int head[maxn],ver[maxn<<1],nxt[maxn<<1],wasted[maxn<<1];
int tot=1;
inline void add(int x,int y)
{
ver[++tot]=y;nxt[tot]=head[x];
head[x]=tot;
}
struct node
{
int num,dep;
};
node nod[maxn];
int del[maxn],stepused[maxn];
bool comp(node a,node b)
{
return a.dep>b.dep;
}
void getdep(int now,int f)
{
nod[now].num=now;nod[now].dep=nod[f].dep+1;
depth[now]=depth[f]+1;
for(register int i=head[now];i;i=nxt[i])
{
if(ver[i]!=f)getdep(ver[i],now);
}
}
void dfs(int now,int last,int step)
{
if(step==d)return;
if(del[now]&&stepused[now]<step)return;
else stepused[now]=step;
del[now]=1;
for(register int i=head[now];i;i=nxt[i])
{
if(ver[i]!=last)dfs(ver[i],now,step+1);
}
}
inline int read()
{
char ch=getchar();int x=0,f=1;
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int main()
{
n=read();d=read();
if(d==1)
{
cout<<n;return 0;
}
for(register int i=1;i<=n-1;i++)
{
int x;x=read();
add(i,x);add(x,i);
}
getdep(0,0);
sort(nod,nod+n,comp);
for(register int i=0;i<=n-1;i++)
{
if(!del[nod[i].num])
{
ans++;
dfs(nod[i].num,nod[i].num,0);
}
}
printf("%d",ans);
return 0;
}