【NOIP模拟赛】LazyChild黑OJ

2014年11月2日1,7520

LazyChild开了一家“善良OJ”。但大多数人都不知道,这其实是家黑OJ。亲爱的同学,请不要惊讶,古时候有黑店,现代为什么不能有黑OJ呢?每AC一道题,网站便会自动在电脑上安装一种木马。LazyChild通过窃取信息获取收益(如网游帐号、OI资料、YuanY和TT的照片等等)。

作为一名资深黑客,老Z某日突然发现,“善良OJ”上的木马,自己电脑上都没有。这可十分让他过意不去。老Z决定通过多A题,来丰富自己电脑的病毒库。

经过调查,老Z发现,很多木马是不能共存的。比如“和谐”木马与“团结”木马,两者只能任选其一。然而,老Z是个完美主义者,他想要自己的病毒库尽可能充实。

老Z不懈的追求最终感动了上天。天上的神仙(半仙?)“牛人雨”给这个问题稍稍降低了一点难度。神仙规定,对于n种木马,有且仅有(n-1)对不能共存,并且对于每种木马,都存在至少一个木马与之不能共存。

老Z不在乎自己AC多少题。请告诉他,他最多能从“善良OJ”上获取木马的个数。

【输入】

第一行,一个正整数n,表示木马个数。

剩余(n-1)行,每行一对木马,表示他们不能共存。(保证相同的木马可以共存,任意不同两行的描述不等价)

木马编号从0至(n-1)

【输入】

一行,老Z最多获得木马的个数。你可以认为开始时没有任何木马。

【输入样例】

3

0 1

1 2

【输出样例】

2

【数据规模】

对于100%的数据,1<=n<=200

题解

这个随便dp吧
f[i][0/1]表示该节点取或不取

 

评论

avatar