Skip to content

1050: 分割海岛

题目

题目描述

在一片海域里面有 $N$ 个海岛连成了树的形状,即互相连通。现在我们想去掉一个海岛 $U$ 把整片连通区域分割成更小的连通区域,并且希望满足每个小连通区域的海岛数量不超过 $k$,请根据输入的海岛区域信息来输出所有可能使分割愿望成立的海岛 $U$ 的编号(保证给出的海岛信息可以构成一棵树)。

输入格式

第 1 行,两个整数 $n$ 和 $k$,代表有 $n$ 个海岛,且每个海岛的编号为 $1,2,\ldots,n$。

第 2~n 行,每行两个整数 $a,b$,代表海岛 $a$ 和海岛 $b$ 之间连通。

输出格式

一行,如果没有符合条件的海岛 $U$,则输出 None,

如果有,从大到小依次输出所有满足条件的海岛 $U$ 的编号,用空格分开。

样例输入

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

样例输出

text 7 1

数据范围

对于百分之三十的数据,$1<k<n\leq 30$

对于百分之六十的数据,$1<k<n\leq 1000$

对于百分之百的数据,$1<k<n\leq 10^5$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!