← 返回题目列表

Codeforces · 2107/D

D. 苹果树穿越

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

一棵苹果树有 $$$n$$$ 个节点,最初每个节点都有一个苹果。你手里有一张纸,最初上面什么也没写。

你正在苹果树上遍历,只要还剩下至少一个苹果,就执行以下操作:

  • 选择一个 苹果路径 $$$(u,v)$$$。路径 $$$(u,v)$$$ 称为 苹果路径 当且仅当路径 $$$(u,v)$$$ 上的每个节点上都有一个苹果。
  • 设 $$$d$$$ 为路径上苹果的数量,在纸上按顺序写下三个数字 $$$(d,u,v)$$$。
  • 然后删除路径$$$(u,v)$$$上的所有苹果。

这里,路径 $$$(u, v)$$$ 指的是从 $$$u$$$ 到 $$$v$$$ 的唯一最短路径上的顶点序列。

设纸上的数字顺序为$$$a$$$。你的任务是找到字典顺序上最大的可能序列$$$a$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个数字 $$$n$$$ ($$$1 \le n \le 1.5 \cdot 10^5$$$)。

每个测试用例的以下 $$$n-1$$$ 行包含两个数字 $$$u,v$$$ ($$$1 \le u,v \le n$$$)。保证输入形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$1.5 \cdot 10^5$$$。

输出

对于每个测试用例,输出字典顺序最大的可能序列 $$$a_1, a_2, \ldots, a_{|a|}$$$。可以证明 $$$|a| \le 3 \cdot n$$$。

示例

输入
复制

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

输出
复制

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

注意

在第一个测试用例中,我们执行以下步骤:

  • 选择苹果路径 $$$(4, 3)$$$。该路径由节点 $$$4, 1, 3$$$ 组成,每个节点都有一个苹果(因此它是有效的苹果路径)。 $$$d = 3$$$ 因为这条路径上有 $$$3$$$ 苹果。按顺序将 $$$3, 4, 3$$$ 添加到我们的序列 $$$a$$$ 中。现在,从这些 $$$3$$$ 顶点中删除苹果。
  • 只有节点 $$$2$$$ 还剩下一个苹果。选择苹果路径 $$$(2, 2)$$$。该路径仅包含单个节点$$$2$$$。 $$$d = 1$$$ 因为这条路径上有 $$$1$$$ 苹果。按顺序将 $$$1, 2, 2$$$ 添加到我们的序列 $$$a$$$ 中,并从 $$$2$$$ 中删除苹果。

最终序列是 $$$[3, 4, 3, 1, 2, 2]$$$。可以证明这是字典顺序上可能的最大序列。