记录编号	552967	评测结果	AAAAAAAAAA
题目名称	[USACO Nov10] 拜访奶牛	最终得分	100
用户昵称	fw	是否通过	通过
代码语言	C++	运行时间	0.172 s
提交时间	2020-08-09 20:00:36	内存使用	15.19 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
inline int read() {
	int s = 0;
	char ch = getchar ();
	while (ch < '0' || ch > '9') ch = getchar ();
	while (ch >= '0' && ch <= '9') s = (s << 3) + (s << 1) + ch - '0',ch = getchar ();
	return s;
}
const int MAXN = 50010;
vector <int> c[MAXN];
int n;
int f[MAXN][2];
void dfs (int u,int fa) {
	f[u][0] = 0;f[u][1] = 1;
	for (int q = 0;q < c[u].size();++ q) {
		int v = c[u][q];
		if (v == fa) continue ;
		dfs (v,u);
		f[u][0] += max (f[v][1],f[v][0]);
		f[u][1] += f[v][0];
	}
	return ;
}
int main () {
	freopen("vacation.in","r",stdin);
	freopen("vacation.out","w",stdout);
	memset (f,0,sizeof (f));
	n = read();
	int nc_from,nc_to;
	for (int q = 1;q < n;++ q) {
		nc_from = read();
		nc_to = read();
		c[nc_from].push_back(nc_to);
		c[nc_to].push_back(nc_from);
	}
	dfs (1,0);
	printf ("%d\n",max (f[1][0],f[1][1]));
	fclose (stdin);
	fclose (stdout); 
	return 0;
}