【bzoj3391】[Usaco2004 Dec]Tree Cutting网络破坏

2014年9月10日1,5780

Description

    约翰意识到贝茜建设网络花费了他巨额的经费,就把她解雇了.贝茜很愤怒,打算狠狠报
复.她打算破坏刚建成的约翰的网络.    约翰的网络是树形的,连接着N(1≤N≤10000)个牛棚.她打算切断某一个牛棚的电源,使和这个牛棚相连的所有电缆全部中断.之后,就会存在若干子网络.为保证破坏够大,每一个子网的牛棚数不得超过总牛棚数的一半,那哪些牛棚值得破坏呢?

Input

    第1行:一个整数N.
    第2到N+1行:每行输入两个整数,表示一条电缆的两个端点.

Output

    按从小到大的顺序,输出所有值得破坏的牛棚.如果没有一个值得破坏,就输出“NONE”.

Sample Input

10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8

Sample Output

3
8
如果牛棚3或牛棚8被破坏,剩下的三个子网节点数将是5,2,2,没有超过5的.
来源信息

题解

为何我写成了tarjan。。。算了当做练习吧。。。

这样成功转化为了模板题