记录编号	28835	评测结果	AAAAAAAAWW
题目名称	[USACO Nov10] 拜访奶牛	最终得分	80
用户昵称	magic	是否通过	未通过
代码语言	C++	运行时间	0.068 s
提交时间	2011-10-17 21:19:33	内存使用	1.60 MiB

#include<iostream>
#include<cstdio>
#define maxlong 50005
	int f[maxlong][2];
	int da[maxlong*2];
	int next[maxlong*2];
	int last[maxlong];
	int tail,n;
using namespace std;
void dfs(int x,int y);
void dfs(int x,int y)
{
	int i,j,a,b;//i dian j ->
	i=da[x];
	j=next[x];
	if (i==0)
	{
		i=da[j];
		j=next[j];
	}
	a=1;
	b=0;
	while (i!=0)
	{
		if (f[i][0]==-1&&y!=i)
		{
			dfs(i,x);
		}
		if (y!=i)
		{
			a+=f[i][0];
			b+=max(f[i][0],f[i][1]);
		}
		i=da[j];
		j=next[j];
	}
	f[x][1]=a;
	f[x][0]=b;
}
void insert(int x,int y);
void insert(int x,int y)
{
	if (next[x]==0)
	{
		tail++;
		da[tail]=y;
		next[x]=tail;
		last[x]=tail;
	}
	else 
	{
		tail++;
		da[tail]=y;
		next[last[x]]=tail;
		last[x]=tail;
	}
}
int max(int x,int y);
int max(int x,int y)
{
	if (x>y) return (x);else return (y);
}
int main()
{
	freopen("vacation.in","r",stdin);
	freopen("vacation.out","w",stdout);
	scanf("%d",&n);
	tail=n;
	int a,b;
	for (int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&a,&b);
		insert(a,b);
		insert(b,a);
	}
	for (int i=1;i<=n;i++)
	{
		f[i][0]=-1;
		f[i][1]=-1;
	}
	dfs(1,0);
	printf("%d",max(f[1][0],f[1][1]));
	return 0;
}