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

Diametrul unui arbore reprezintă lungimea drumului (ca numar de noduri) intre cele mai departate două frunze.

Diametrul unui arbore reprezintă lungimea drumului intre cele mai departate două frunze.

h2. Cerinţă

Dându-se un arbore cu $N$ noduri, să se determine diametrul acestuia.

Dându-se un arbore cu N noduri, să se determine diametrul acestuia.

h2. Date de intrare

h2. Exemplu

table(example). |_. darb.in |_. darb.out |

|_. darb.in |_. darb.out |

|11
1 2
1 3

h3. Explicaţie

!problema/darb?diametruarbore2.png!
 

Cel mai lung lanţ al arborelui este din frunza 9 în 11 şi are dimensiunea 8.
h2. 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 <tex>O(N^2)</tex> ce obţine $40$ puncte şi poate fi găsită 'aici':job_detail/1093859?action=view-source.

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 <tex>O(N^2)</tex> ce obţine $30$ puncte şi poate fi găsită "aici":http://www.infoarena.ro/job_detail/1085868?action=view-source.

'Soluţia de 100 de puncte':job_detail/1085869?action=view-source 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 <tex>O(N)</tex>.

"Soluţia de 100 de puncte":http://www.infoarena.ro/job_detail/1085869?action=view-source se bazează pe două parcurgeri in lăţime 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 <tex>O(N)</tex>.

== include(page="template/taskfooter" task_id="darb") ==