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了，可以的话，请您参考添加页面，与大家一起分享你的题解！