记录编号	34222	评测结果	AAAAAAAAAA
题目名称	[USACO Nov10] 拜访奶牛	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.242 s
提交时间	2011-12-05 10:15:18	内存使用	58.11 MiB

#include <fstream>
using namespace std;
ifstream fin("vacation.in");
ofstream fout("vacation.out");
int n;
int C[50001][301],f[50001],g[50001];
bool bo[50001];

int Max(int o1,int o2)
{
	return (o1>o2?o1:o2);	
}

void Init()
{
int S,E,i;
	fin>>n;
	for(i=1;i<n;i++)
	{
		fin>>S>>E;
		C[S][++C[S][0]]=E;
		C[E][++C[E][0]]=S;
	}
	
}

int dp(int pos)
{
int i;
	bo[pos]=true;
	for(i=1;i<=C[pos][0];i++)
		if(bo[C[pos][i]]==false)
		{
			int O;
			O=dp(C[pos][i]);
			g[pos]+=Max(O,g[C[pos][i]]);
			f[pos]+=g[C[pos][i]];
		}
	f[pos]+=1;
	return f[pos];
}

int main()
{
	Init();
	
	dp(1);
	
	fout<<Max(f[1],g[1])<<endl;
	
	fin.close();
	fout.close();
	return 0;
}