贪心40pts
查看原帖
贪心40pts
232507
OK咯莫名其妙楼主2021/8/24 09:45
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
struct node{
	int u,v,nxt;
}edge[maxn];
int head[maxn],n,tot,fa[maxn],vis[maxn],dep[maxn],ans;
void add(int u,int v){
	edge[++tot].u=u;
	edge[tot].v=v;
	edge[tot].nxt=head[u];
	head[u]=tot;
}
queue<int> q;
stack<int> s;
void bfs(){
	q.push(1);
	s.push(1);
	dep[1]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=edge[i].nxt){
			int y=edge[i].v;
			if(y==fa[x]) continue;
			dep[y]=dep[x]+1;
			q.push(y);
			s.push(y);
		}
	}
}
 
void dfs(int now,int depth){
	if(depth>2)return ;
	vis[now]=1;
	for(int i=head[now];i;i=edge[i].nxt){
		dfs(edge[i].v,depth+1);
	}
}
void work(){
	while(!s.empty()){
		int x=s.top();
		s.pop();
		if(!vis[x]){
			ans++;
			dfs(fa[fa[x]],0);
		}
	}
}
int main(){
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		cin>>fa[i];
		add(i,fa[i]);
		add(fa[i],i);
	}
	bfs();
	work();
	cout<<ans<<endl;
	return 0;
}
2021/8/24 09:45
加载中...