记录编号	80244	评测结果	AAAAAAAAAA
题目名称	[USACO Nov10] 拜访奶牛	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.118 s
提交时间	2013-11-06 22:03:27	内存使用	4.30 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int SIZEN=50001;
vector<int> c[SIZEN];
int father[SIZEN]={0};
int f[SIZEN]={0},g[SIZEN]={0};//f是选本节点,g是不选本节点
//f是将所有子节点的g值加起来再+1,g是将所有子节点的max(f,g)加起来
int n;
void DP(int x){
	if(x!=1&&c[x].size()==1){//叶子节点
		f[x]=1;
		g[x]=0;
		return;
	}
	int i,u;
	for(i=0;i<c[x].size();i++){
		u=c[x][i];
		if(u==father[x]) continue;
		DP(u);
		f[x]+=g[u];
		g[x]+=max(f[u],g[u]);
	}
	f[x]++;
}
void DFS(int x){
	int i,u;
	for(i=0;i<c[x].size();i++){
		u=c[x][i];
		if(u==father[x]) continue;
		father[u]=x;
		DFS(u);
	}
}
void read(void){
	scanf("%d",&n);
	int i,u,v;
	for(i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		c[u].push_back(v);
		c[v].push_back(u);
	}
}
int main(){
	freopen("vacation.in","r",stdin);
	freopen("vacation.out","w",stdout);
	read();
	DFS(1);
	DP(1);
	printf("%d\n",max(f[1],g[1]));
	return 0;
}