Cerere

cerere

==Include(page="template/taskheader" task_id="cerere")==

== include(page="template/taskheader" task_id="cerere") ==

In tara maimutelor scotiene arborele genealogic este bine definit deoarece de o bucata buna de timp nu a mai murit nici o maimuta. Maimutele au adesea nemultumiri insa numai anumite maimute sunt destul de inteligente incat sa le rezolve. In momentul in care maimuta numarul $i$ are o nemultumire si nu o poate rezolva ea trebuie sa prezinte o cerere in scris celui de-al $K{~i~}$-lea stramos al ei si numai acestuia. La randul lui, acesta (sa-l numim $j$) trebuie sa o trimita celui de-al $K{~j~}$-lea stramos al sau, in cazul in care n-o poate rezolva, si tot asa pana cand o maimuta inteligenta va primi cererea.

Poveste ...

h2. Cerinta

Dandu-se arborele genealogic al maimutelor sa se gaseasca pentru fiecare dintre ele pe la cate maimute trece cererea pana va fi rezolvata.

...

h2. Date de intrare
 
Pe prima linie a fisierului de intrare se afla un numar intreg N reprezentand numarul de maimute. A doua linie a fisierului contine $N$ numere, $K{~1~} K{~2~} ... K{~n~}$ cu semnificatia din enunt (se garateaza ca exista al $K{~i~}$-lea stramos pentru fiecare maimuta $i$). Daca $K{~i~}$ este $0$ atunci maimuta numarul $i$ poate rezolva cereri. Maimuta care este stramosul tuturor celorlalte maimute (radacina arborelui genealogic) este cea mai inteleapta maimuta si deci va putea rezolva cereri.

h2. Restrictii

Urmatoarele $N-1$ linii vor contine cate doua numere, separate printr-un spatiu, $A$ si $B$ cu semnificatia: maimuta $A$ este tatal maimutei $B$.

...

h2. Date de iesire

h2. Date de intrare

Pe prima linie a fiserului de iesire se vor gasi $N$ numere $G{~1~} G{~2~} ... G{~n~}, G{~i~}$ reprezentand numarul de maimute pe la care trece cererea maimutei numarul {~i~} (excluzand-o pe aceasta).

...

h2. Restrictii

h2. Date de iesire

* $2 ≤ N ≤ 100 000$

...

h2. Exemplu

table(example). |_. cerere.in |_. cerere.out |
| 10
0 1 0 2 2 0 2 2 1 2
1 2
1 6
2 3
2 4
4 5
6 7
6 8
7 9
7 10
| 0 1 0 1 2 0 1 1 2 1 |
 
==Include(page="template/taskfooter" task_id="cerere")==
 

| cerere.in | cerere.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="cerere") ==

240