Tree Factory
Contest: Technocup 2020 - Elimination Round 2
Difficulty rating: 2500
Tags: constructive algorithms, greedy, trees

Bytelandian Tree Factory produces trees for all kinds of industrial applications. You have been tasked with optimizing the production of a certain type of tree for an especially large and important order.

The tree in question is a rooted tree with $$$n$$$ vertices labelled with distinct integers from $$$0$$$ to $$$n - 1$$$. The vertex labelled $$$0$$$ is the root of the tree, and for any non-root vertex $$$v$$$ the label of its parent $$$p(v)$$$ is less than the label of $$$v$$$.

All trees at the factory are made from bamboo blanks. A bamboo is a rooted tree such that each vertex has exactly one child, except for a single leaf vertex with no children. The vertices of a bamboo blank can be labelled arbitrarily before its processing is started.

To process a bamboo into another tree a single type of operation can be made: choose an arbitrary non-root vertex $$$v$$$ such that its parent $$$p(v)$$$ is not a root either. The operation consists of changing the parent of $$$v$$$ to its parent's parent $$$p(p(v))$$$. Note that parents of all other vertices remain unchanged, in particular, the subtree of $$$v$$$ does not change.

Efficiency is crucial, hence you have to minimize the number of operations to make the desired tree from a bamboo blank. Construct any optimal sequence of operations to produce the desired tree.

Note that the labelling of the resulting tree has to coincide with the labelling of the desired tree. Formally, the labels of the roots have to be equal, and for non-root vertices with the same label the labels of their parents should be the same.

It is guaranteed that for any test present in this problem an answer exists, and further, an optimal sequence contains at most $$$10^6$$$ operations. Note that any hack that does not meet these conditions will be invalid.

Input format:
The first line contains a single integer $$$n$$$ — the number of vertices in the tree ($$$2 \leq n \leq 10^5$$$).

The second line contains $$$n - 1$$$ integers $$$p(1), \ldots, p(n - 1)$$$ — indices of parent vertices of $$$1, \ldots, n - 1$$$ respectively ($$$0 \leq p(i) < i$$$).

Output format:
In the first line, print $$$n$$$ distinct integers $$$id_1, \ldots, id_n$$$ — the initial labelling of the bamboo blank starting from the root vertex ($$$0 \leq id_i < n$$$).

In the second line, print a single integer $$$k$$$ — the number of operations in your sequence ($$$0 \leq k \leq 10^6$$$).

In the third line print $$$k$$$ integers $$$v_1, \ldots, v_k$$$ describing operations in order. The $$$i$$$-th operation consists of changing $$$p(v_i)$$$ to $$$p(p(v_i))$$$. Each operation should be valid, i.e. neither $$$v_i$$$ nor $$$p(v_i)$$$ can be the root of the tree at the moment.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
5
0 0 1 1

Example output:
0 2 1 4 3
2
1 3

Example input:
4
0 1 2

Example output:
0 1 2 3
0

Editorial:
Let's solve the problem backwards: given a tree, transform it into a bamboo with reverse operations. A reverse operation in this context looks like this: given a vertex $$$v$$$ and its two distinct children $$$u$$$ and $$$w$$$, make $$$w$$$ the parent of $$$u$$$.
What's the lower bound on the number of operations we need to make? We can see that the depth of the tree, i.e. the length of the longest vertical path starting from the root, can increase by at most one per operation. On the other hand, the depth of the bamboo is $$$n - 1$$$. Therefore, we'll need to make at least $$$n - 1 - (\text{initial depth of the tree})$$$ operations.
This number would always be enough if for any non-bamboo tree we could find an operation that would increase its depth. And indeed we can: consider a longest path starting from the root. If all its vertices have at most one children, the tree is a bamboo and we are done. Otherwise, take any vertex $$$v$$$ on the path with at least two children, its child $$$u$$$ on the longest path, and any other child $$$w$$$, then make $$$w$$$ the parent of $$$u$$$. One can see that there is a longer path now.
One efficient way to do these operations successively is to keep track of the lowest candidate for $$$u$$$. After applying an operation, the candidate is either $$$u$$$ again, or one of its ancestors. With standard amortized analysis, we can now perform all these operations in $$$O(n)$$$ time.
To output the answer, print the labelling of the final bamboo you obtain, followed by the reverse sequence of the operations you've made.