记录编号	27526	评测结果	AAAAAAAAAA
题目名称	[USACO Nov10] 拜访奶牛	最终得分	100
用户昵称	donny	是否通过	通过
代码语言	C++	运行时间	0.064 s
提交时间	2011-09-26 19:28:30	内存使用	1.42 MiB

#include <iostream>
#include <fstream>

using namespace std;

int i,j,k,l;
int f[50010][2],next[101000],a[101000];
int n,p,q;
int head,tail;

int Max(int x,int y)
{
	if (x>y)
		return x;
	return y;
}

void insert(int x,int y)
{
	if (next[x]==0)
	{
		if (a[x]==0)
			a[x]=y;
		else
		{
			tail++;
			a[tail]=y;
			next[x]=tail;
		}
	}
	else
	{
		tail++;
		a[tail]=y;
		next[tail]=next[x];
		next[x]=tail;
	}
	
	if (next[y]==0)
	{
		if (a[y]==0)
			a[y]=x;
		else
		{
			tail++;
			a[tail]=x;
			next[y]=tail;
		}
	}
	else
	{
		tail++;
		a[tail]=x;
		next[tail]=next[y];
		next[y]=tail;
	}
}

void dfs(int x,int y)
{
	int i,j,k,l;
	i=a[x];
	j=next[x];
	k=1;
	l=0;
	
	while (i!=0)
	{
		if ((f[i][0]==-1)and(i!=y))
			dfs(i,x);
		if (i!=y)
		{
			k+=f[i][0];
			l+=Max(f[i][1],f[i][0]);
		}
		i=a[j];
		j=next[j];
	}
	f[x][0]=l;
	f[x][1]=k;
}

int main()
{
	ifstream fin("vacation.in");
	ofstream fout("vacation.out");
	
	fin>>n;
	
	tail=n;
	for (i=1;i<n;i++)
	{
		fin>>j>>k;
		insert(j,k);
	}
	
	for (i=1;i<=n;i++)
	{
		f[i][0]=-1;
		f[i][1]=-1;
	}
	
	dfs(1,0);
	
	if (f[1][1]>f[1][0])
		f[1][0]=f[1][1];
	
	fout<<f[1][0]<<endl;
	
	fin.close();
	fout.close();
	
	return 0;
}