Skip to content

1451: Life on a tree

题目

题目描述

交大有 $n$ 幢宿舍楼。由于大家生活在树上,因此 $n$ 幢宿舍楼之间的通路形成一棵树,每条边的边权都是 $1$。

为了能及时挽救被半期考试折磨的可怜人,现在需要选择一些宿舍楼建立医疗点存放足量的速效救心丸。选择的要求是:

  • 每幢宿舍楼都能到达一个距离不超过 $k$ 的医疗点。
  • 在这个前提下,建立的医疗点数量尽可能少。

请输出一种可行的方案。

Input

请从 stdin 读入。

输入第一行为两个正整数,$n, k ~ (1 \leq n \leq 5 \times 10 ^ 5, 0 \leq k \lt n)$。

接下来 $n - 1$ 行,第 $i$ 行有两个正整数 $u_i, v_i (1 \leq u_i, v_i \leq n)$,表示树上有一条 $u_i$ 到 $v_i$ 的边。

对于 $70$ 分的数据,$n \leq 1000$。Hint: $O(n ^ 2)$.

另有 $25$ 分的数据,$n \leq 100000$。Hint: $O(n ^ {1.5})$.

Output

请输出到 stdout 中。

输出第一行为你选择的点数量 $x$,第二行为 $x$ 个整数表示选择的方案中的点的标号。

如果有多种方案,输出任意一种即可。

Sample Input

6 1 1 2 2 3 3 4 4 5 5 6

6 3 1 2 2 3 3 4 4 5 5 6

13 3 1 2 2 3 3 4 4 5 5 6 6 7 7 8 2 9 1 10 10 11 11 12 12 13

Sample Output

2 2 5

1 3

2 5 10

Constraints

Time Limit: 0.5s

Memory Limit: 512MB

Oops! 本题目还没有解答!

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

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

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