记录编号	27594	评测结果	AAAAAAAAAA
题目名称	[USACO Nov10] 拜访奶牛	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	0.079 s
提交时间	2011-09-27 08:44:28	内存使用	0.46 MiB

#include <fstream>

#define I_F "vacation.in"
#define O_F "vacation.out"

const int MAXn=50000;

struct rtn
{
	int a, b;
}ans;
struct lb
{
	int x;
	lb *next;
}*map[MAXn]={NULL};
int n;

void Input();
rtn Dfs(const int, const int);
void Output();

int main()
{
	Input();
	ans=Dfs(0,-1);
	Output();
	return 0;
}

void Input()
{
	lb *temp;
	int x,y;
	std::ifstream fin(I_F);
	fin>>n;
	for (short i=1; i<n; i++)
	{
		fin>>x>>y;
		x--, y--;
		temp=map[x];
		map[x]=new lb;
		map[x]->x=y;
		map[x]->next=temp;
		temp=map[y];
		map[y]=new lb;
		map[y]->x=x;
		map[y]->next=temp;
	}
	fin.close();
}

rtn Dfs(const int x, const int l)
{
	rtn r={1,0}, t;
	for (lb *i=map[x]; i!=NULL; i=i->next)
		if (i->x!=l)
		{
			t=Dfs(i->x,x);
			r.a+=t.b;
			r.b+=(t.a>t.b)?t.a:t.b;
		}
	return r;
}

void Output()
{
	std::ofstream fout(O_F);
	fout<<(int)((ans.a>ans.b)?ans.a:ans.b)<<std::endl;
	fout.close();
}