← 返回题目列表

AtCoder · abc414_f

F. 跳跃旅行

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

你有一棵树 N 顶点编号自 1 to N 和一个整数 K。的 i第一条边双向连接顶点 u_i 和 v_i.

您当前位于顶点 1。您可以重复以下操作零次或多次:

  • 选择一个顶点,其与您当前所在顶点的距离为 K,然后移动到该顶点。这里,两个顶点之间的距离是连接两个顶点的简单路径中的边的数量。

对于每个 k=2,\ldots,N,判断是否可以移动到顶点 k 通过重复操作,如果可以移动,求最少操作次数。

你有 T 测试用例,因此解决每个用例。

约束

  • 1\leq T\leq 10^5
  • 2\leq N\leq 2\times 10^5
  • 1\leq K\leq 20
  • 1\leq u_i\lt v_i\leq N
  • 给定的图是一棵树。
  • 总和 N 所有测试用例最多 2\times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出,其中 \mathrm{case}_i 表示 i- 第一个测试用例。 总共

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N K
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

输出

输出 T 行。的 i- 第行应包含以下问题的答案 i-第一个测试用例,格式如下:

\mathrm{ans}_2 \mathrm{ans}_3 \ldots \mathrm{ans}_N

\mathrm{ans}_i 是以下问题的答案 k=i。如果你可以移动到顶点 i 通过重复操作, \mathrm{ans}_i 是最小操作次数;否则, \mathrm{ans}_i is -1.


示例输入 1

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

示例输出 1

-1 1 1 -1 2

此示例输入/输出由一个测试用例组成。

距顶点距离的顶点 1 is 2 是顶点 3 和 4,这样就可以通过一次操作移动到这两个顶点。

另外,通过从顶点移动 1 到顶点 4,然后移动到顶点 6 到顶点的距离 4 is 2,可以移动到顶点 6 有两个操作。

您无法移动到顶点 2 和 5 无论您如何执行操作。


示例输入 2

3
2 20
1 2
10 2
1 9
1 8
1 5
6 8
4 5
2 8
5 10
7 9
3 5
10 1
2 6
2 9
8 9
9 10
3 9
4 9
7 9
1 6
3 5

示例输出 2

-1
1 1 1 -1 1 1 -1 -1 1
2 4 4 5 1 4 4 3 4