斜堆的插入历史

题目背景

斜堆（Skew Heap）是一种实现优先队列的二叉树。它不要求保持平衡，也不要求左孩子小于右孩子，但始终满足堆序性质：每个节点的值都小于它的所有孩子。

现在给出一棵由若干次插入操作形成的斜堆。你需要还原一种可能的插入顺序；若存在多种可能，输出字典序最小的一种。

题目描述

一棵斜堆是一棵满足如下性质的二叉树：

• 每个节点的值都小于它的孩子；
• 左右子树之间没有大小关系要求；
• 树不要求平衡。

向一棵斜堆 H 中插入一个新元素 X 的过程定义如下。所有元素互不相同。

情况一：基础情况

若 H 为空，或者 X 小于 H 的根节点，则：

• X 成为新的根节点；
• 原来的整棵 H 成为 X 的左子树；
• X 的右子树为空。

示意如下：

Insert(X, H)  =>      X
                     /
                    H

情况二：递归情况

若 X 大于 H 的根节点 Y，设 Y 原来的左、右子树分别为 A、B，则：

1. 交换 Y 的左右子树；
2. 将 X 递归插入交换后的左子树，也就是原来的右子树 B。

示意如下：

        Y                         Y
       / \                       / \
      A   B       =>    Insert(X,B) A

给定最终斜堆的结构。树中共有 n 个节点，节点编号为 0,1,...,n-1，每个编号恰好出现一次。由于满足堆序性质，编号为 0 的节点一定是根节点。

对于每个节点 i（1 <= i < n），使用一个整数 parent[i-1] 表示它与父节点的关系：

• 若 parent[i-1] = p 且 0 <= p < 100，表示节点 i 是节点 p 的左孩子；
• 若 parent[i-1] = 100+p，表示节点 i 是节点 p 的右孩子。

输入保证所描述的树可以由上述插入操作得到。

请输出一种能够生成该斜堆的插入顺序。若存在多种合法顺序，输出其中字典序最小的一种。

两个长度相同的序列 A、B 比较字典序时，找到第一个满足 A_i != B_i 的位置：若 A_i < B_i，则称 A 的字典序更小。

输入格式

第一行包含一个整数 n，表示斜堆中的节点数。

第二行包含 n-1 个整数：

parent[0] parent[1] ... parent[n-2]

其中 parent[i-1] 描述节点 i 与其父节点的关系。

输出格式

输出一行 n 个整数，表示字典序最小的合法插入顺序。

样例 1

输入

7
100 0 101 102 1 2

输出

0 1 2 3 4 5 6

说明

最终得到的斜堆为：

        0
       / \
      2   1
     / \ / \
    6  4 5  3

样例 2

输入

7
100 0 2 102 4 104

输出

4 6 5 2 0 1 3

说明

插入序列 4 6 5 2 0 1 3 和 6 4 5 2 0 1 3 都能生成给定斜堆，因此输出字典序更小的前者。

样例 3

输入

8
0 100 1 102 2 3 5

输出

2 5 0 3 4 6 7 1

样例 4

输入

2
0

输出

0 1

样例 5

输入

21
100 1 101 103 3 4 6 107 7 0 10 11 110 12 112 111 8 108 2 16

输出

8 18 17 7 9 0 11 6 12 4 16 3 15 1 20 2 10 5 13 19 14

数据范围

• 2 <= n <= 51；
• 对于第二行中从 0 开始编号的第 i 个数，有：
  • 0 <= parent[i] <= i，或
  • 100 <= parent[i] <= 100+i；
• parent 中没有两个元素相同；
• 若 100+k 出现在 parent 中，则 k 也一定出现在 parent 中；
• 输入保证描述的是一棵能够完全由插入操作构造出的合法斜堆。