记录编号	28750	评测结果	AAAAAAAAAA
题目名称	[USACO Nov10] 拜访奶牛	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.198 s
提交时间	2011-10-17 10:20:25	内存使用	1.46 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int f[50005][2],n,sum[50005];
vector<int>v[50005];
bool fl[50005];

void dfs(int now)
{
    int i,j;
	sum[now]=1;
	f[now][1]=1;
	for(i=0;i<v[now].size();i++)
	{
		j=v[now][i];
		if(sum[j]==0)
		{	
			dfs(j);
			f[now][1]+=min(f[j][1],f[j][0]);
			f[now][0]+=f[j][1];
		}
	}
}
 
int main()
{
	int i,a,b;
	freopen("vacation.in","r",stdin);
	freopen("vacation.out","w",stdout);
	scanf("%d",&n);
	for(i=0;i<n-1;i++)
	{
		scanf("%d%d",&a,&b);
		a--;
		b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(0);
	printf("%d\n",n-min(f[0][0],f[0][1]));
	return 0;
}