#E. 先序遍历

    传统题 2000ms 512MiB

先序遍历

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

按照 “根 - 左 - 右” 的顺序遍历 二叉树 :

  • 先序遍历 = 根 + 左子树先序遍历 + 右子树先序遍历
  • 空树的先序遍历 = 空

例如,如下这棵树先序遍历的结果为 FBADCEGIH\text{FBADCEGIH}

给一棵 nn 个点的二叉树(根节点为 11),你可以进行如下操作 至多 11

  • 选择 11 个 (除了根以外的)点 uu ,断开 𝑢𝑢 和其父节点之间的边;
  • 然后重新选择另一个点作为 𝑢𝑢 的父节点、将 𝑢𝑢 接上去,需要保证操作之后仍然是一棵以 11 为根的二叉树

你想要操作之后的二叉树有字典序最小的先序遍历序列,输出这个序列。

输入描述

第一行 11 个整数 𝑇𝑇,代表有 𝑇𝑇 组数据。 每组数据共 n+1n + 1 行。第一行 11 个整数 𝑛𝑛,表示节点的个数。接下来 𝑛𝑛 行,第 𝑖𝑖22 个整数 𝑙𝑠[𝑖],𝑟𝑠[𝑖]𝑙𝑠[𝑖], 𝑟𝑠[𝑖] 代表 𝑖𝑖 号结点的左右儿子编号,没有左右儿子的话用 00 表示

输出描述

输出 𝑇𝑇 行,对于每组数据,输出一行 𝑛𝑛 个整数,代表字典序最小的二叉树先序遍历

输入样例1

12
4
2 3
0 4
0 0
0 0
5
2 3
0 4
0 5
0 0
0 0
6
5 2
3 6
4 0
0 0
0 0
0 0
6
2 3
6 4
0 5
0 0
0 0
0 0
6
5 2
3 0
4 0
6 0
0 0
0 0
6
3 2
4 6
0 0
5 0
0 0
0 0
6
4 2
5 3
0 0
0 0
0 6
0 0
6
3 2
0 0
5 4
0 6
0 0
0 0
6
2 3
0 0
5 4
0 6
0 0
0 0
6
3 2
4 5
0 0
0 6
0 0
0 0
6
2 3
0 4
0 0
0 5
0 6
0 0
6
2 5
3 4
0 0
0 0
6 0
0 0

输出样例1

1 2 3 4
1 2 3 4 5
1 2 3 4 5 6
1 2 4 3 5 6
1 2 3 4 6 5
1 2 4 5 3 6
1 2 5 4 6 3
1 2 3 5 4 6
1 2 3 4 5 6
1 2 4 3 6 5
1 2 3 4 5 6
1 2 3 4 5 6

样例解释

对于第一个样例,可以把 33 号结点连在 22 号结点的左儿子处。

对于第二个样例,可以把 44 号结点连在 33 号结点的左儿子处 。

数据范围

测试点编号 nn\leq 特殊性质
131 \sim 3 1010
484 \sim 8 200200
9119 \sim 11 10001000
121412 \sim 14 105 10^5 所有的 ls[i]=0ls[i] = 0
1515 10510^5 所有的 rs[i]=0rs[i] = 0
162016 \sim 20

对于所有测试点:令 n\sum n 代表数据中 nn 的总和, 1T100,1n1051 \leq T \leq 100, 1 \leq n \leq 10^5, 1n3×1051\leq \sum n \leq 3 \times 10^5,保证输入数据是一棵以 11 为根的二叉树。

卉图编程奥赛部CSP-J 第二轮模拟赛(补)

未参加
状态
已结束
规则
OI
题目
5
开始于
2024-7-30 8:00
结束于
2024-7-30 11:30
持续时间
3.5 小时
主持人
参赛人数
6