Creating Offices

题目描述

有 n 个城市和它们之间的 n-1 条道路。任意两座城市之间存在唯一的一条路径，它们之间的距离等于该路径上道路的条数。 一家公司希望在若干城市设立办事处，但任意两座办事处之间的距离必须至少为 d。问他们最多可以设立多少个办事处？

输入格式

第一行输入包含两个整数 n 和 d：城市数量和最小距离。城市编号为 1,2,$\dots$,n。 接下来有 n-1 行描述道路。每行包含两个整数 a 和 b：表示城市 a 与城市 b 之间有一条道路。

输出格式

首先输出一个整数 k：最多可设立的办事处数量。接着输出将要设立办事处的城市编号。你可以输出任意一个合法的解。

5 3
1 2
2 3
3 4
3 5

2
1 4

提示

$1 \le n,d \le 2 \cdot 10^5$ $1 \le a,b \le n$

标签: CSES1752|高级图论问题

来源

CSES1752|高级图论问题