萌新求助灵异事件
查看原帖
萌新求助灵异事件
398190
lanretE楼主2023/2/8 14:56

如果把 dfs 里面 int maxxint 去掉,样例3就会错,不去掉就能过,这是为什么

#include<iostream>
using namespace std;
const int N=1e5+10;
int n,k,a[N],ans;
int ne[N<<1],he[N],ver[N<<1],tot;
void add(int u,int v){
	ver[++tot]=v;
	ne[tot]=he[u];
	he[u]=tot;
}
int maxx;
int dfs(int u,int fa,int dep){
	int maxx=dep; 
	for(int i=he[u];i;i=ne[i]){
		int v=ver[i];
		if(v==fa) continue;
		maxx=max(maxx,dfs(v,u,dep+1));
	}	
	if(maxx-dep==k-1 && a[u]!=1){
		++ans; return 0;
	} 
	return maxx;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	if(a[1]!=1) ++ans,a[1]=1;
	for(int i=2;i<=n;++i){
		add(i,a[i]); add(a[i],i);
	}
	dfs(1,0,0);
	printf("%d\n",ans);
	return 0;
}
2023/2/8 14:56
加载中...