Amazing Tree#13030

Amazing Tree (Editorial)

Author:

Andrei Constantinescu

As always, when we want to find the lexicographically minimal order of something, we should do it greedily in a left-to-right fashion. It's clear that the first element will be one of the leaves, and for any leaf we can construct a post-order with this leaf as the first element. Let be the leaf with the minimum id, and be its only neighbour. To construct a post-order with as the first element, we have to go from the (yet unknown) root straight to , and the last vertex we will visit before is ( itself can't be the root). After visiting we will return to , and there can be two possibilities:

  • itself is the root. Then we have to visit all other neighbours of first, and finish in . It's clear that we need to visit the neighbours in increasing order of the minimum leaf in them.

  • is not the root. Then we have to visit all neighbours of , except and the one leading to the root, then write down in the post-order, and then go up.

Since we can choose where the root will be, we can reformulate the greedy as follows:

  • We have to visit all neighbours of , except and the one with the largest min leaf.

  • Then, either traverse the remaining subtree or put in the order and continue in the remaining neighbour.

We did it only on the first step, but it is not hard to see that it works like that in the future also: we have arrived at from , that's all that is important.

The implementation can be made much easier if you root the tree in the min leaf, because now you will always go down the tree.