← 返回题目列表

AtCoder · arc170_f

F. 边缘删除 2

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

分数: 1000 点

问题陈述

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

对于排列 P=(P_1,\ldots,P_N) of (1,2,\ldots,N),我们定义序列 A(P) 如下:

  • A(P) 最初是空的。写 每个顶点上的 P_i 在每个顶点上 i.
  • 对于 i=1,2,\ldots,N 按此顺序执行以下操作:
    • 如果顶点 i 是一个孤立的顶点,追加 0 到年底 A(P)。否则,选择具有最小写入整数的相邻顶点。将写入所选顶点的整数附加到末尾 A(P) 并删除连接顶点的边 i 和选定的顶点。

在所有可能的序列中找到字典顺序最小的序列 A(P).

解决每个问题 T 给出的测试用例。

约束

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 1\leq u_i,v_i\leq N
  • 给定的图是一棵树。
  • 所有输入数字均为整数。
  • 总和 一个输入文件中的 N 单个输入中的所有测试用例最多 2 \times 10^5.

输入

输入由标准输入按以下格式给出:

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

每个案例均按以下格式给出:

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

输出

打印 T 行。的 i第行 (1 \leq i \leq T) 应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

3
5
1 2
2 3
2 4
4 5
8
8 6
7 2
2 1
3 7
5 6
1 6
4 3
7
7 1
5 2
1 2
6 5
4 1
5 3

示例输出 1

1 2 0 1 3
1 2 2 3 1 4 0 0
1 2 2 0 3 0 4

在第一个测试用例中,对于 P=(4,1,2,3,5),可以获得 A(P)=(1,2,0,1,3) 如下:

  • 与顶点相邻的顶点 1 最小的写入整数是顶点 2。追加 P_2=1 到年底 A(P) 并删除连接顶点的边 1 和 2.

  • 与顶点相邻的顶点 2 最小的写入整数是顶点 3。追加 P_3=2 到年底 A(P) 并删除连接顶点的边 2 和 3.

  • 顶点 3 是一个孤立的顶点,所以追加 0 到年底 A(P).

  • 与顶点相邻的顶点 4 最小的写入整数是顶点 2。追加 P_2=1 到年底 A(P) 并删除连接顶点的边 4 和 2.

  • 与顶点相邻的顶点 5 最小的写入整数是顶点 4。追加 P_4=3 到年底 A(P) 并删除连接顶点的边 5 和 4.

可以证明这是所有可能序列中字典序最小的序列 A(P).