题目名称	593. [USACO Nov10] 拜访奶牛
输入输出	`vacation.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2011-09-23加入
开放分组	全部用户
提交状态
分类标签
	分享题解

通过：34，提交：67，通过率：50.75%
数声风笛ovo	100	0.044 s	17.09 MiB	C++
筽邝	100	0.047 s	2.50 MiB	Pascal
Ezio	100	0.049 s	1.18 MiB	C++
C语言入门	100	0.057 s	1.50 MiB	Pascal
Satoshi	100	0.061 s	1.32 MiB	C++
传奇	100	0.062 s	1.07 MiB	Pascal
TARDIS	100	0.062 s	1.26 MiB	C++
donny	100	0.064 s	1.42 MiB	C++
王者自由	100	0.067 s	1.59 MiB	C++
HouJikan	100	0.069 s	1.89 MiB	C++

本题关联比赛
20110923
20110923
20191218

关于拜访奶牛的近10条评论(全部评论)
f [ i ] [ 0 ] += max ( f [ i ] [ 0 ] , f [ i ] [ 1 ] ) 不访问当前节点，也可以不访问相邻的节点否则 30 分 fw 2020-08-09 20:02 6楼
我感觉像记忆化搜索？？？？？传奇 2014-11-07 08:56 5楼
回复 @HouJikan : 神犇请赐予我神力吧。 Ezio 2014-09-19 18:22 4楼
我想着直接最大独立集不就行了么QAQ 蒟蒻最不喜欢dp了 HouJikan 2014-09-19 17:09 3楼
不要忘记最后Max（f[1],g[1]）因为忘了写这个，错了4组数据 QhelDIV 2011-12-05 10:16 2楼
树形DP，填根节点时先填其儿子节点，全题设一号节点为根节点。 f[i][1]表示拜访奶牛i所得到的最大拜访量。 f[i][0]表示不拜访奶牛i所得到的最大拜访量。用了递归。目标状态为：f[1][0]与f[1][1]中大的一个。 Truth.Cirno 2011-11-09 18:03 1楼

593. [USACO Nov10] 拜访奶牛

★☆ 输入文件：vacation.in 输出文件：vacation.out 简单对比
时间限制：1 s 内存限制：128 MiB

经过了几周的辛苦工作,贝茜终于迎来了一个假期.作为奶牛群中最会社交的牛,她希望去拜访N(1<=N<=50000)个朋友.这些朋友被标号为1..N.这些奶牛有一个不同寻常的交通系统,里面有N-1条路,每条路连接了一对编号为C1和C2的奶牛(1 <= C1 <= N; 1 <= C2 <= N; C1<>C2).这样,在每一对奶牛之间都有一条唯一的通路.

FJ希望贝茜尽快的回到农场.于是,他就指示贝茜,如果对于一条路直接相连的两个奶牛,贝茜只能拜访其中的一个.当然,贝茜希望她的假期越长越好,所以她想知道她可以拜访的奶牛的最大数目.

输入格式:

第1行:单独的一个整数N

第2..N行:每一行两个整数,代表了一条路的C1和C2.

样例输入(vacation.in):

6 2

3 4

2 3

1 2

7 6

5 6

输入说明:

贝茜认识7只奶牛,其中6和2相连,3和4相连,等等...最后形成这么一个网络:

1--2--3--4

5--6--7

输出格式:

第一行:单独的一个整数,代表了贝茜可以拜访的奶牛的最大数目.

样例输出(vacation.out):

输出解释:

{1,3,5,7}或{1,4,5,7}或{2,4,5,7}

【数码范围】

40%数据 n<=100