P11322 [NOISG 2020 Qualification] Firefighting

在 Mouseopolis，这座鼠国的大都会，一场大火席卷了整座城市。为了防止类似灾难再次发生，鼠国的国王 Squeaky 决定在鼠国的城镇中建立消防站。

鼠国由 $N$ 个城镇组成，编号为 $1$ 到 $N$。城镇之间通过 $N-1$ 条双向道路连接，每条道路连接两个城镇，并且道路的长度可能不同。城镇网络保证任何两个城镇之间都可以通过某些道路相连。 为了有效扑灭火灾，国王的顾问认为消防站到火灾发生地点的距离不得超过 $K$ 公里，否则火势将难以控制。然而，建设消防站的成本较高，国王希望尽可能减少消防站的数量。 任务是确定在鼠国的哪些城镇建设消防站，以使得需要建设的消防站数量最少。

- 第一行包含两个整数 $N$ 和 $K$，分别表示城镇的数量和消防站的最大服务距离。 - 接下来的 $N-1$ 行，每行包含三个整数 $A_i, B_i, D_i$，表示城镇 $A_i$ 和城镇 $B_i$ 之间有一条长度为 $D_i$ 公里的双向道路。

- 第一行包含一个整数 $F$，表示需要建设的最少消防站数量。 - 第二行包含 $F$ 个整数，表示建设消防站的城镇编号。 可以按任意顺序输出。如果有多种可行方案，输出任意一种即可。

【样例解释】 对于样例 #1，最少需要在城镇 $1, 8, 3, 6$ 建立消防站，以保证每个城镇到最近的消防站的距离不超过 $4$ 公里。 对于样例 #2，最少需要在城镇 $5, 6, 2, 3$ 建立消防站。 对于样例 #3，必须在每个城镇建立消防站。 对于样例 #4，可以在城镇 $4$ 和 $10$ 建立消防站，或者选择其他符合条件的方案。 【数据范围】 - $1 \leq N \leq 3 \times 10^5$ - $1 \leq K \leq 10^{15}$ - $1 \leq A_i, B_i \leq N$ - $1 \leq D_i \leq 10^9$ | 子任务编号 | 分值 | 限制条件 | |:--------:|:---------:|:--------------------------:| | $1$ | $3$ | $K \leq 20$，且 $D_i \geq 30$ | | $2$ | $5$ | $N \leq 17, K \leq 17$，且 $D_i = 1$ | | $3$ | $9$ | $N \leq 17, K \leq 10^6$，且 $D_i \leq 10^4$ | | $4$ | $19$ | $K \leq 30$，且 $D_i \geq 20$ | | $5$ | $26$ | $N \leq 3 \times 10^3$ | | $6$ | $38$ | 无额外限制 |