Fişierul intrare/ieşire:zvon.in, zvon.outSursăHappy Coding 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test1.5 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Zvon

Directorul unei filiale a unei mari companii a aflat un zvon conform caruia presedintele companiei a decis sa desfiinteze filiala respectiva si sa concedieze toti angajatii filialei (inclusiv pe director). Fiind in relatii bune cu angajatii sai, directorul a decis sa isi anunte angajatii intr-un timp cat mai scurt, pentru ca acestia sa isi poata gasi cat mai repede un alt loc de munca. Angajatii filialei sunt organizati intr-o structura ierarhica arborescenta. In varful ierarhiei se afla directorul, care are cativa subordonati directi. Acestia au la randul lor alti subordonati directi s.a.m.d. pana la cel mai umil angajat, care nu are nici un subordonat. Zvonul concedierii se propaga, astfel, din varful ierarhiei, pana la baza ei. La un minut dupa ce a aflat zvonul, directorul poate da un telefon si isi poate anunta unul din subordonati. Dupa inca un minut, directorul isi poate anunta inca un subordonat, pana cand sunt anuntati toti subordonatii sai. La randul sau, fiecare subordonat, imediat dupa ce afla zvonul, asteapta un minut pana sa isi anunte unul din subordonatii proprii, apoi inca unul pana sa isi anunte un alt subordonat s.a.m.d. Angajatii care nu au subordonati nu anunta pe nimeni. Este evident ca ordinea de anuntare a subordonatilor influenteaza durata de timp dupa care toti angajatii afla zvonul. Determinati durata de timp minima din momentul in care directorul a aflat zvonul, dupa care toti angajatii pot afla zvonul.

Date de intrare

Prima linie a fisierului de intrare zvon.in contine numarul intreg T, reprezentand numarul de teste. In continuare, urmeaza descrierea celor T teste. Pe prima linie din cadrul fiecarui test se afla numarul intreg N, reprezentand numarul de angajati. Urmatoarele N-1 linii contin cate doua numere intregi diferite a si b, avand semnificatia ca b este un subordonat direct al lui a.

Date de iesire

Pentru fiecare test afisati in fisierul de iesire zvon.out cate o linie continand durata de timp minima dupa care toti angajatii pot afla zvonul.

Restrictii

  • 1 ≤ T ≤ 57
  • 1 ≤ N ≤ 100 000
  • Angajatii sunt numerotati de la 1 (directorul) la N.

Exemplu

zvon.inzvon.out
3
1
3
1 2
1 3
5
1 2
1 3
3 4
3 5
0
2
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content