## DIY Christmas Tree

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You have been mailed a disassembled Christmas tree. In the box, there were three things: a set of branches, a drawing of a tree with nodes in total, and a set of safety instructions.

Each branch can be attached to one other branch. The attachment relationship between two branches can be described as follows: if you attach a branch to another branch , is considered a child of . Each branch also has a distinct weight, which is represented by an integer from to .

The safety instructions state:

• Every branch except the lightest branch should be attached to another branch.
• Start by placing the lightest branch at the top of your tree.
• Add all the remaining branches in a predetermined order, one at a time.
• When adding a branch with a weight of , find the heaviest branch already added to the assembled tree which is strictly lighter than . Attach the weight branch to the one found. If the found branch already has children (attached branches), place it to the right side of all of its children.

Before you start, you realize that you must add the branches in a specific order so that the resulting tree will match the diagram's tree.

#### Input Specification

On the first line, read one integer . holds for all cases, and holds for 15% of the points.

The following lines depict an adjacency list of the diagram, where the th line begins with a single integer denoting the number of children of node , where . Following is a space, and more space separated integers on the same line. Each integer () indicates that node is a child of .

It is guaranteed that the tree will be rooted at .

Please note that for the second section of input, the ordering of children matters. Values of are given from left to right, and the tree created by your program's output is to match this. Additionally, the values of should be considered meaningless other than to make reading the input easier. The diagram consists of branches which are unidentified other than by their position relative to other branches.

If you are still confused, please consult the sample input.

#### Output Specification

Print a permutation of the numbers in the range , such that the assembled tree matches the one given in the input. We assert that two trees match if, when simultaneously traversing both in a depth-first manner, the number of children contained by the th branch in one tree is equal to the number of children contained by the th branch of the other tree for all possible values of .

If there are multiple possible answers, output any one of them (only one).
If there is no answer, output a single integer .

Again, consult the samples for more clarification.

#### Sample Input 1

3
2 2 3
0
0

#### Sample Output 1

1 3 2

#### Explanation for Sample 1

The diagram's tree looks like this:

By starting with the branch with weight , then adding branch , you get this:

You can see that the two trees are structurally equivalent. Remember, numbers don't matter.

In this case, the given answer is the only valid answer. For example, adding the branches in the order would produce a different tree:

#### Sample Input 2

7
1 2
2 3 4
1 6
1 7
0
1 5
0

#### Sample Output 2

1 2 5 6 3 7 4

#### Explanation for Sample 2

The tree looks like this:

As you can see, it probably works.

• commented on June 26, 2018, 7:25 a.m. edited

HELP :: My code, WA, notepad.pw/DIY

• commented on Jan. 1, 2016, 10:40 p.m.

Hi, is the second output right? Mustn't it be 1 2 5 6 7 3 4?

• commented on Jan. 1, 2016, 10:41 p.m.

If you believe there are multiple possible answers, print any of them.

• commented on Jan. 1, 2016, 10:45 p.m.

thanks for answering, the output2 is the answer of the assembling shown below?

• commented on Jan. 1, 2016, 10:48 p.m.

Yes, sample output 2 is correct. It produces the desired tree, as shown.

• commented on Jan. 1, 2016, 4:11 p.m.

?

• commented on Jan. 1, 2016, 4:15 p.m.

There are N branches in total, where each one has a distinct weight in the range of 1 to N. For example, in sample 1, N=3 so there are three branches which have weights 1, 2, and 3.