Constructing a Tree
Time limit2sMemory limit1024 MB
Given a Prüfer-like sequence produced by always removing the largest leaf, decide whether exactly one tree generates it and print that tree's edges in lexicographic order, else -1.
- Level
Medium7 of 10
- Topics
- Tree, Greedy, Implementation, Heap
- Solved
- No attempts yet
Problem
There is a tree with N vertices, numbered 1 through N. From this tree we build a sequence of (N-2) positive integers as follows.
- Among the vertices of degree 1, pick the one with the largest number. Call this vertex x.
- Append to the sequence the number of the vertex adjacent to x.
- Delete from the tree the edges incident to x.
- Repeat steps 1 through 3 a total of (N-2) times.
Given a sequence {a1, ..., aN-2}, find a tree from which this sequence can be produced by the procedure above.
Input
The input is given as follows.
N
a1 . . . aN-2
Output
If such a tree exists, print its (N-1) edges according to the following rules.
- Each edge must be printed in the form a b with a < b.
- The edges must be printed in lexicographic order. That is, for any two edges (a1, b1) and (a2, b2), if a1 < a2, or if a1 = a2 and b1 < b2, then edge (a1, b1) must be printed before edge (a2, b2).
If no tree exists, or if two or more trees exist, print -1.
Constraints
- 3 ≤ N ≤ 500,000
- 1 ≤ ai ≤ N (1 ≤ i ≤ N-2)