贪心20分求条
查看原帖
贪心20分求条
1141876
wzyc楼主2025/7/22 10:40
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
typedef long long ll; 
int n=0;
struct node
{
	int d,f;
	vector<int> e;
}a[N];
struct cmp
{
	bool operator()(int x,int y)const
	{
		return a[x].d>a[y].d;
	}
};
set<int,cmp> se;
set<int,cmp>::iterator it;
bool b[N]={};
void dfs(int x)
{
	int i=0;
	for(i=0;i<a[x].e.size();i++)
	{
		if(!b[a[x].e[i]])
		{
			a[a[x].e[i]].d=a[x].d+1;
			b[x]=1;
			a[a[x].e[i]].f=x;
			dfs(a[x].e[i]);
		}
	}
}
void dfs2(int x,int d)
{
	if(d==3)
		return;
	int i=0;
	for(i=0;i<a[x].e.size();i++)
	{
		se.erase(a[x].e[i]);
		dfs2(a[x].e[i],d+1);
	}
}
int main()
{
	int i=0,x=0,sum=0;
	cin>>n;
	for(i=2;i<=n;i++)
	{
		cin>>x;
		a[i].e.push_back(x);
		a[x].e.push_back(i);
	}
	b[1]=1;
	a[1].f=1;
	dfs(1);
	for(i=1;i<=n;i++)
		se.insert(i);
	while(!se.empty())
	{
		x=*se.begin();
		se.erase(se.begin());
		dfs2(a[a[x].f].f,1);
		sum++;
	}
	cout<<sum;
}
2025/7/22 10:40
加载中...