P2475 [SCOI2008] Skew Heap

Sichuan 2008 NOI Qualifier.

A skew heap is a commonly used data structure. It is also a binary tree and satisfies the same heap property as a binary heap: every non-root node has a value larger than its parent. Therefore, in the whole skew heap, the root has the minimum value. A skew heap does not need to be balanced, and there is no restriction on the relative sizes of the left and right children of any node. In this problem, all values in the skew heap are distinct. To insert a new element $X$ into a skew heap $H$, proceed recursively: when $H$ is empty or $X$ is smaller than the root of $H$, $X$ becomes the new root, and the original root (if any) becomes the left child of $X$. When $X$ is greater than the root of $H$, swap the two subtrees of the root, and (recursively) insert $X$ into the left subtree after the swap. You are given a skew heap that contains each of the values $0, 1, \dots, n$ exactly once. Find a sequence of nodes such that this skew heap can be obtained by inserting these nodes one by one into an empty tree. If multiple answers exist, output the lexicographically smallest one. The input is guaranteed to have a solution.

The first line contains an integer $n$. The second line contains $n$ integers $d_1, d_2, \dots, d_n$. $d_i < 100$ means $i$ is the left child of $d_i$, and $d_i \ge 100$ means $i$ is the right child of $d_i - 100$. Obviously $0$ is always the root, so $d_0$ does not appear in the input.

Output a single line containing $n+1$ integers, i.e., the lexicographically smallest insertion sequence.

Constraints: $2 \le n \le 50$. Translated by ChatGPT 5