Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-01-16 22:11:18.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | darb.in, darb.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Diametrul unui arbore
Diametrul unui arbore reprezintă numărul de noduri de pe cel mai lung drum dintre două frunze.
Cerinţă
Dându-se un arbore cu N noduri, să se determine diametrul acestuia.
Date de intrare
Pe prima linie a fisierului darb.in se afla N cu specificatiile de mai sus. Pe următoarele N-1 linii se află muchiile arborelui.
Date de ieşire
În fişierul de ieşire darb.out se va afisa diametrul arborelui.
Restricţii
- 2 ≤ N ≤ 100.000
Exemplu
| darb.in | darb.out |
|---|---|
| 11 1 2 1 3 1 4 2 5 3 6 4 7 5 8 5 9 6 10 10 11 | 8 |
Explicaţie
Cel mai lung lant al arborelui este din frunza 9 in 11 si are dimensiunea 8.
Indicaţii de rezolvare
O prima soluţie care ne vine în minte este să facem o parcurgere in lăţime din fiecare nod al arborelui şi să reţinem cea mai lungă distanţă parcursă. Această soluţie are complexitatea 
.
Trebuie sa te autentifici pentru a trimite solutii. Click aici
