贪心10pts求助(玄关)
查看原帖
贪心10pts求助(玄关)
1287433
__ycy1124__楼主2024/7/18 17:05
#include<bits/stdc++.h>
using namespace std;
vector <int> a[1001];
struct Node{
	int h,i,y;
	bool bj;
}cyc[1001];
struct ycy{
	int i;
	int h;
	int las1;
	int las2;
};
bool cmp(Node x1,Node x2){
	return x1.h>x2.h;
}
queue <ycy> q;
void bfs(int p,int h,int las1,int las2){
	if(p==0){
		return;
	}
	cyc[p].h=h;
	cyc[p].i=p;
	cyc[p].y=las2;
	for(auto ccy:a[p]){
		if(!cyc[ccy].bj){
			q.push({ccy,h+1,p,las1});
			cyc[ccy].bj=1;
		}
	}
}
void dfs(int p,int js){
	cyc[p].bj=0;
	if(js==2){
		return; 
	}
	for(auto it:a[p]){
		dfs(it,js+1);
	}
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u;
		scanf("%d",&u);
		a[i+1].push_back(u);
		a[u].push_back(i+1);
	}
	q.push({1,0,1,1});
	while(!q.empty()){
		bfs(q.front().i,q.front().h,q.front().las1,q.front().las2);
		q.pop();
	}
	sort(cyc+1,cyc+n+1,cmp);
	int ans=0;
	for(int i=1;i<=n;i++){
		if(cyc[i].bj){
			ans++;
			dfs(cyc[i].y,0);
		}
	}
	printf("%d",ans);
	return 0;
}
2024/7/18 17:05
加载中...