Fişierul intrare/ieşire:cerere.in, cerere.outSursăpreONI 2005 Runda 2
AutorDan-Ionut FecheteAdăugată de
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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 Ki-lea stramos al ei si numai acestuia. La randul lui, acesta (sa-l numim j) trebuie sa o trimita celui de-al Kj-lea stramos al sau, in cazul in care n-o poate rezolva, si tot asa pana cand o maimuta inteligenta va primi cererea.

Cerinta

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

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, K1 K2 ... Kn cu semnificatia din enunt (se garateaza ca exista al Ki-lea stramos pentru fiecare maimuta i). Daca Ki 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.

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

Date de iesire

Pe prima linie a fiserului de iesire se vor gasi N numere G1 G2 ... Gn, Gi reprezentand numarul de maimute pe la care trece cererea maimutei numarul i (excluzand-o pe aceasta).

Restrictii

  • 2 ≤ N ≤ 100 000

Exemplu

cerere.incerere.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content