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 翻译