AT_arc170_f.[ARC170F] Edge Deletion 2

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。树的第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$，为无向边。

对于 $1$ 到 $N$ 的一个排列 $P=(P_1,\ldots,P_N)$，定义数列 $A(P)$ 如下：

• $A(P)$ 初始为空。对每个顶点 $i$，在顶点 $i$ 上写下 $P_i$。
• 按照 $i=1,2,\ldots,N$ 的顺序，依次进行以下操作：
  • 如果顶点 $i$ 是孤立点，则在 $A(P)$ 的末尾添加 $0$。
  • 否则，从与顶点 $i$ 相邻的顶点中，选择写有最小整数的顶点。将该顶点上写的整数添加到 $A(P)$ 的末尾，并删除顶点 $i$ 与该顶点之间的边。

请你在所有可能的 $A(P)$ 中，求出字典序最小的一个。

给定 $T$ 组测试数据，请分别输出答案。

输入按以下格式从标准输入读入：

$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$ 行输出第 $i$ 个测试用例的答案。

数据范围

• $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$

样例解释 1

对于第 $1$ 个测试用例，$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$ 是孤立点，因此在 $A(P)$ 末尾添加 $0$。
• 顶点 $4$ 相邻顶点中，写有最小整数的是顶点 $2$。将 $P_2=1$ 添加到 $A(P)$ 末尾，并删除顶点 $4$ 与顶点 $2$ 的边。
• 顶点 $5$ 相邻顶点中，写有最小整数的是顶点 $4$。将 $P_4=3$ 添加到 $A(P)$ 末尾，并删除顶点 $5$ 与顶点 $4$ 的边。

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

由 ChatGPT 4.1 翻译