| 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ă lungimea drumului (ca numar de noduri) intre cele mai departate 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ă cate o pereche de numere a si b reprezentând 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 lanţ al arborelui este din frunza 9 în 11 şi 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 
ce obţine 40 puncte şi poate fi găsită aici.
Soluţia de 100 de puncte se bazează pe două parcurgeri in lăţime/adâncime pornind cu prima parcurgere dintr-un nod oarecare şi continuând cu a doua din ultimul nod în care am ajuns. Astfel, cea mai îndepărtată frunză din prima parcurgere reprezintă un capăt al lanţului, urmând să îi găsim celălalt capăt în ultimul nod în care ajungem in a doua parcurgere având o complexitate 
.
