| Fișierul intrare/ieșire | prepost.in, prepost.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | din folclor | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 0.05 sec | Limită de memorie | 4096 KB |
| Scorul tău | N/A | Dificultate |
  1.75
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Prepost
Fie un arbore general cu rădăcină cu N noduri numerotate de la 1 la N. Se cunosc parcurgerile sale în preordine și în postordine, date sub forma a câte unui vector cu N elemente. Să se reconstituie muchiile arborelui, indicând pentru fiecare nod cine este părintele lui.
Date de intrare
Fișierul de intrare prepost.in conține pe prima linie numărul de noduri N. Pe a doua linie se găsește o permutare a mulțimii { 1, 2, ..., N } indicând parcurgerea în preordine. Pe a treia linie se găsește o altă permutare a mulțimii { 1, 2, ..., N } indicând parcurgerea în postordine.
Date de ieșire
În fișierul de ieșire prepost.out se vor tipări N numere. Al i-lea număr indică părintele nodului i. Pentru rădăcină se va tipări valoarea 0.
Restricții
- 1 ≤ N ≤ 100.000
Exemplu
| prepost.in | prepost.out |
|---|---|
| 8 4 3 1 5 7 8 6 2 3 5 7 1 2 6 8 4 |
4 6 4 0 1 8 1 4 |
Explicație
