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

#include <iostream>
#include <cstdio> 
#include <cstdlib>
using namespace std;

int N;
int Mat[100001][51];
int Profit[100001];
int Abut[100001]={0}; 
int F[100001][2];
bool used[100001]={0};

int max(int a,int b)
{
	return a>b?a:b;
}

void init()
{
	scanf("%d",&N);
	for (int i=1;i<=N;i++)
	{
		F[i][1]=1;
	} 
	
	int a,b;
	for (int i=1;i<=N-1;i++)
	{
		scanf("%d%d",&a,&b);
		Abut[a]++;
		Mat[a][Abut[a]]=b;
		Abut[b]++;
		Mat[b][Abut[b]]=a;
	}
}

void dynamic(int x)  //dynamic programming
{
	used[x]=true;
	for (int i=1;i<=Abut[x];i++)
	{
		if( !used[ Mat[x][i] ] )
		{
			dynamic(Mat[x][i]);
			F[x][0]+=max( F[ Mat[x][i] ][0] ,  F[ Mat[x][i] ][1] );
			F[x][1]+=F[ Mat[x][i] ][0];
		}
	}
}

int main()
{
	freopen("vacation.in","r",stdin);
	freopen("vacation.out","w",stdout);
	init();
	dynamic(1);
	
	if(F[1][1]>F[1][0] )
		cout<<F[1][1]<<endl;
	else
		cout<<F[1][0]<<endl;
	return 0;
}