Mai intai trebuie sa te autentifici.
Diferente pentru problema/darb intre reviziile #42 si #19
Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="darb") ==
Diametrul unui arbore reprezintălungimea drumului(ca numarde noduri)intre celemai departate două frunze.
Diametrul unui arbore reprezintă numărul de noduri de pe cel mai lung drum dintre 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
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.
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.
h2. Date de ieşire
h2. Restricţii
* $2 ≤$N$≤ 100.000$
* $2 ≤ N ≤ 100.000$
h2. Exemplu
table(example).|_. darb.in |_. darb.out | |11
|_. darb.in |_. darb.out | | 11
1 2 1 3 1 4
5 8 5 9 6 10
10 11 |$8$|
10 11 | 8 |
h3. Explicaţie
!problema/darb?diametruarbore2.png!
Cel mai lung lant al arborelui este din frunza 9 in 11 si are dimensiunea 8.
Celmai lung lanţal arboreluiestedinfrunza9 în 11 şi aredimensiunea 8.
h3. Indicaţii de rezolvare
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. '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>.
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>.
== include(page="template/taskfooter" task_id="darb") ==