记录编号	27549	评测结果	AAAAAAAAAA
题目名称	[USACO Nov10] 拜访奶牛	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.067 s
提交时间	2011-09-26 20:23:20	内存使用	1.59 MiB

#include <cstdio>
const int MAXN = 50002;
int last[MAXN], pre[MAXN*2], edg[MAXN*2], top;
int n, c1, c2, f[MAXN], g[MAXN];
inline int max(int a, int b) {
    return a>b ? a : b;
}
void DP(int x) {
    int i = last[x];
    f[x] = 1;
    while(i != 0) {
        if(f[edg[i]] == 0) {
            DP(edg[i]);
            f[x] += g[edg[i]];
            g[x] += max(g[edg[i]], f[edg[i]]);
        }
        i = pre[i];
    }
}
int main() {
    freopen("vacation.in","r",stdin);
    freopen("vacation.out","w",stdout);
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d %d", &c1, &c2);
        pre[++top] = last[c1];
        edg[last[c1] = top] = c2;
        pre[++top] = last[c2];
        edg[last[c2] = top] = c1;
    }
    DP(1);
    printf("%d\n", max(f[1], g[1]));
    return 0;
}