h2. 'Razboiul lumilor':problema/razboi

Solutia optima are complexitate $O(N)$ si se realizeaza parcurgand arborele de $2$ ori. La prima parcurgere fixam radacina arborelui in nodul $1$. Vom calcula pentru fiecare nod $i$ cate $2$ valori: lungimea maxima a unui drum de la orasul $i$ la orice alt oras din subarborele acestuia, {$L{~1~}[i]}, si a lungimea maxima a unui drum de la orasul $i$ la un oras din subarborele acestuia, dar care este diferit de primul drum, {$L{~2~}[i]} (practic, a doua lungime maxima a unui drum, care poate fi, eventual, egala cu lungimea primului). In a doua parcurgere vom calcula distanta maxima de la fiecare oras $i$ la orice alt oras si vom alege orasele pentru carea aceasta distanta maxima este minima. Pentru radacina arborelui am calculat deja aceasta valoare din prima parcurgere. Pentru orice alt nod $i$, distanta maxima de la $i$ la orice alt oras este ori {$L{~1~}[i]}, ori un drum ce trece prin parintele lui $i$. Cel mai lung drum ce trece prin parintele lui $i$ are lungimea egala cu distanta de la $i$ la parintele lui $i$ plus {$L{~1~}[parinte[i]]}, in cazul in care drumul corespunzator lui {$L{~1~}[parinte[i]]} nu trece prin orasul $i$, respectiv plus {$L{~2~}[parinte[i]]}, in cazul in care drumul corespunzator lui {$L{~1~}[parinte[i]]} trece prin orasul $i$.

Solutia optima are complexitate $O(N)$ si se realizeaza parcurgand arborele de $2$ ori. La prima parcurgere fixam radacina arborelui in nodul $1$. Vom calcula pentru fiecare nod $i$ cate $2$ valori: lungimea maxima a unui drum de la orasul $i$ la orice alt oras din subarborele acestuia, {$L{~1~}[i]$}, si lungimea maxima a unui drum de la orasul $i$ la un oras din subarborele acestuia, dar care este diferit de primul drum, {$L{~2~}[i]$} (practic, a doua lungime maxima a unui drum, care poate fi, eventual, egala cu lungimea primului). In a doua parcurgere vom calcula distanta maxima de la fiecare oras $i$ la orice alt oras si vom alege orasele pentru carea aceasta distanta maxima este minima. Pentru radacina arborelui am calculat deja aceasta valoare din prima parcurgere. Pentru orice alt nod $i$, distanta maxima de la $i$ la orice alt oras este ori {$L{~1~}[i]$}, ori un drum ce trece prin parintele lui $i$. Cel mai lung drum ce trece prin parintele lui $i$ are lungimea egala cu distanta de la $i$ la parintele lui $i$ plus {$L{~1~}[parinte[i]]$}, in cazul in care drumul corespunzator lui {$L{~1~}[parinte[i]]$} nu trece prin orasul $i$, respectiv plus {$L{~2~}[parinte[i]]$}, in cazul in care drumul corespunzator lui {$L{~1~}[parinte[i]]$} trece prin orasul $i$.
A doua solutie are complexitatea $O(N*logN)$ si este o generalizare a solutiei pentru cazul in care toate muchiile arborelui au aceeasi lungime. Solutia pentru cazul muchiilor cu lungimi egale are complexitate $O(N)$ si se bazeaza pe o eliminare repetata a tuturor frunzelor din arbore. Se elimina primul strat de frunze, obtinandu-se un arbore mai mic, apoi se repeta procedeul pana cand arborele ramas are unul sau doua noduri (aceste noduri fiind nodurile cautate). In cazul in care muchiile au lungimi diferite, vom privi arborele dinspre exterior spre interior. Fiecarui nod $i$ din arbore ii corespunde un subarbore care are toate nodurile mai aproape de exterior decat nodul $i$. Vom elimina si de aceasta data frunzele, pe rand. Pentru fiecare nod $i$ vom calcula $dmax[i]$ ca fiind lungimea celui mai lung drum de la nodul $i$ la o frunza din subarborele sau (aceasta valoare reprezinat distanta nodului $i$ fata de exteriorul arborelui). La fiecare pas vom elimina un nod $i$ ramas frunza (deoarece toate nodurile din subarborele sau au fost deja eliminate anterior) pentru care $dmax[i]$ este minim (eliminam frunza cea mai apropiata de exteriorul arborelui initial). Repetam procedeul pana ramanem cu un nod sau cu $2$ noduri.  Pentru a obtine complexitate mentionata putem folosi un heap.

h2. 'Divizor si multiplu':problema/divmul