分数: 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