卡常求助
查看原帖
卡常求助
174469
zero4338楼主2020/5/31 10:23

一直有三个点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;
}
2020/5/31 10:23
加载中...