5085. 「POI2019 R3」地铁 Metro

传统 $500 - 10000\ \text{ms}$ $256\ \text{MiB}$

题目描述

题目译自 XXVI Olimpiada Informatyczna – III etap Metro

拜托城的道路网络由 $n$ 个交叉口和连接它们的 $n-1$ 条双向道路组成，允许在所有交叉口之间通行。市长 Bajtazar 计划在城市中建设地铁。在某些交叉口将设立地铁站，某些道路下方将铺设隧道，供超高速列车通行。地铁网络需保持连通，即地铁必须能够在任意两站之间直接或间接通行。

建设终点站的成本相当高，即那些仅有一条隧道的站点（因为它们需配备支持列车停靠和维护的相应基础设施）。因此，决定终点站的数量最多为 $k$ 。为使地铁网络有意义，至少需建设两个终点站。

乘客的烦躁系数定义为从其居住的交叉口到最近地铁站所需经过的最少道路数。需规划地铁网络，使所有交叉口居民的最大烦躁系数尽可能小。

第一行包含两个整数 $n$ , $k$ ( $n \geq 3$ , $2 \leq k \leq n$ )，分别表示交叉口数和终点站的最大数量。交叉口编号为 $1$ 至 $n$ 。

接下来的 $n-1$ 行，每行包含两个整数 $a$ , $b$ ( $1 \leq a, b \leq n$ , $a \neq b$ )，表示交叉口 $a$ 和 $b$ 间存在道路。

第一行输出两个整数 $r$ , $s$ ( $2 \leq s \leq k$ )，分别表示最小的烦躁系数和所选地铁网络的终点站数量。

第二行输出 $s$ 个互不相同的整数（范围 $[1, n]$ ），表示终点站所在的交叉口编号。

需选择 $r$ 最小的网络。若 $r$ 相同，优先选择 $s$ 最小的网络。若仍有多种方案，输出任意一种。

输入

输出

1 2
1 8

道路网络如图所示。最优地铁网络有两个终点站（交叉口 $1$ 和 $8$ ），烦躁系数为 $1$ 。存在其他满足 $r=1$ , $s=2$ 的网络，也有 $r=1$ , $s=3$ 的网络，但后者非最优，因 $s$ 未最小化。

$n=30$ , $k=29$ ，交叉口 $2, \ldots, n$ 均与交叉口 $1$ 相连。
$n=5000$ , $k=4000$ ，交叉口 $1, 2, \ldots, 2000$ 连成线，交叉口 $2001, \ldots, 3500$ 连至 $1$ ，交叉口 $3501, \ldots, 5000$ 连至 $2000$ 。
$n=2^{20}-1$ , $k=1509$ ，交叉口形成完全二叉树。

若仅第一行输出正确，可获 $50\%$ 的分数，但程序需在时间和内存限制内正常结束。

详细子任务附加限制及分值如下表所示。