记录编号	33149	评测结果	AAAAAAAAAA
题目名称	[USACO Nov10] 拜访奶牛	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.103 s
提交时间	2011-11-09 16:42:55	内存使用	21.34 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define max(a,b) ((a)>=(b)?(a):(b))
using namespace std;
int w[100001],n,m;
int q[100001][2],a[100001][51];
int ji[100001]={0},answer;
bool used[100001]={0};
void dp(int x);
int main()
{
	freopen ("vacation.in","r",stdin);
	freopen ("vacation.out","w",stdout);
	scanf("%d",&n);
	for (int o=1;o<=n;o++)
	{
		q[o][1]=1;
	}
	for (int o=1;o<=n-1;o++)
	{
		int c,d;
		scanf("%d%d",&c,&d);
		ji[c]++;
		ji[d]++;
		a[c][ji[c]]=d;
		a[d][ji[d]]=c;
	}
	dp(1);
	if (q[1][0]<q[1][1])
	{
		cout<<q[1][1];
	}
	else
	{
		cout<<q[1][0];
	}
	return 0;
}
void dp(int x)
{
	used[x]=1;
	for (int i=1;i<=ji[x];i++)
	{
 		if (!used[a[x][i]])
		{
			dp(a[x][i]);
			q[x][0]+=max(q[a[x][i]][0],q[a[x][i]][1]);
			q[x][1]+=q[a[x][i]][0];
		}
	}
}