h2. Enunt

Acum ne vom concentra asupra sarcinii initiale, de determinare a valorii de maxim/minim. Enuntul este urmatorul:

Acum ne vom concentra asupra intrebarii initiale, de determinare a valorii de maxim/minim. Enuntul este urmatorul:

Fie $G = (V, E)$ un graf neorientat conex, $|E| = |V| - 1$. Vom considera, bineinteles, ca fiecare nod $x &#8712; V$ are asociata o valoare $value[x]$ din multimea numerelor reale. Se dau $M$ instructiuni, $M <= 200000$, de doua tipuri : primul tip cere sa se scrie maximul dintre valorile nodurilor ce se afla pe lantul dintre $x, y &#8712; V$ (daca $P = (x{~0~},x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y$,  atunci se cere $&#916; = Maxim {value[u] | u &#8712; P}$), iar al doilea tip modifica valoarea asociata unui nod.

# Retine fiecare lant ca un vector $Path[].array[]$ cu noduri ordonate crescator dupa adancime si pastreaza un pointer catre nodul din lantul sau parinte $Path[].parent$;
# Pentru fiecare nod retine lantul caruia apartine $whatPath[]$ si pozitia in vectorul lantului $whatPos[]$.

Este evident ca memoria ocupata este $O(N)$, fiecare nod fiind inclus intr-un singur lant. Numarul maxim de lanturi prin care putem trece pornind din radacina pana intr-una din frunze, este $O(sqrt(N))$.
 
!heavy-path-decomposition?Figura2.JPG!

Este evident ca memoria ocupata este $O(N)$, fiecare nod fiind inclus intr-un singur lant. Numarul maxim de lanturi prin care putem trece pornind din radacina pana intr-una din frunze, este $O(sqrt(N))$.