比赛 20110923 评测结果 MMMMMMMMMM
题目名称 拜访奶牛 最终得分 0
用户昵称 magic 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-09-23 20:50:24
显示代码纯文本
#include<iostream>
#include<cstdio>

using namespace std;
struct Node
{
	int son[1000];
	int p;
};
	Node node[50005];
	int num[50005];
	int nod[50005];
	bool flag[50005];
	int a,b,n,ans=0;
void qsort(int a[],int l,int r);	
void qsort(int a[],int l,int r)
{
	int i,j,x,y;
	i=l;j=r;x=a[(l+r)/2];
	while (i<=j)
	{
		while (a[i]<x) i++;
		while (a[j]>x) j--;
		if (i<=j)
		{
			y=a[i];a[i]=a[j];a[j]=y;
			y=nod[i];nod[i]=nod[j];nod[j]=y;
			i++;j--;
		}
	}
	if (l<j) qsort(a,l,j);
	if (i<r) qsort(a,i,r);
}
int main()
{
	freopen("vacation.in","r",stdin);
	freopen("vacation.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		nod[i]=i;
	}
	for (int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&a,&b);		
		num[a]++;
		num[b]++;
		node[a].p++;
		node[b].p++;
		node[a].son[node[a].p]=b;
		node[b].son[node[b].p]=a;
	}
	qsort(num,1,n);
	for (int i=1;i<=n;i++)
	{
		if (!flag[i])
		{
			ans++;
			for (int j=1;j<=node[i].p;j++)
			{
				flag[node[i].son[j]]=1;
			}
		}
	}
	/*for (int i=1;i<=n;i++)
	{
		printf("%d ",num[i]);
	}
	for (int i=1;i<=n;i++)
	{
		printf("%d ",nod[i]);
	}*/
	printf("%d",ans);
	return 0;
}