h3(#solutie-descompunere-brute). Solutia $O(M*N)$

Sunt o multitudine de solutii simple ce ne pot trece prin minte. Pentru cea aleasa de mine voi retine un vector $parent[]$ semnificand parintele unui nod calculat printr-un $depth-search$, si $depth[]$ ce retine adancimea, adica numarul de muchii de la radacina pana la nodul interogat. Cu ajutorul lor, prima cerinta se rezolva in $O(N)$ astfel: merg "in sus" in arbore pana cand voi ajunge in cel mai apropiat stramos comun, retinand pe parcurs valoare maxima ceruta. Rezolvarea cerintei a doua se face simplu in $O(1)$ modificand direct $value[]$.

Sunt o multitudine de solutii simple ce ne pot trece prin minte. Pentru cea aleasa de mine voi retine un vector $parent[]$ semnificand parintele unui nod calculat printr-un $depth-search$, si un vector $depth[]$ ce retine adancimea, adica numarul de muchii de la radacina pana la nodul interogat. Cu ajutorul lor, prima cerinta se rezolva in $O(N)$ astfel: merg "in sus" in arbore pana cand voi ajunge in cel mai apropiat stramos comun, retinand pe parcurs valoarea maxima ceruta. Rezolvarea cerintei a doua se face simplu in $O(1)$ modificand direct $value[]$.

h3(#solutie-log-sqrt). Solutia $O(M*log(N)*sqrt(N))$

!heavy-path-decomposition?Figura3.jpg!

Complexitatea finala: $O(M log^2^(N))$. In practica, aceasta tehnica se comporta foarte bine si poate fi folosita cu succes. Singurul inconvenient este numarul mare de linii de cod scrie.

Complexitatea finala: $O(M log^2^(N))$. In practica, aceasta tehnica se comporta foarte bine si poate fi folosita cu succes. Singurul inconvenient este numarul mare de linii de cod scrise.

h2(#aplicatii). Aplicatii