p=. !heavy-path-decomposition?fig1.jpg!

Astfel, s-a construit vectorul $seq[]$ care are urmatoarea proprietate: &#34;daca $&#916; = &#8721; seq[i]$, $firstPos[x] <= i <= firstPos[y]$, x fiind un stramos al lui y, atunci &#916; reprezinta $&#8721; value[u]$, $u &#8712; P$, $P = (x{~0~}, x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y&#34;$. Conform acesteia, daca vom determina cel mai apropiat stramos comun dintre doua noduri, atunci nu va fi nevoie decat de o structura de date ce permite calcularea intr-un mod eficient a sumei pe un interval din $seq[]$ si modificarea unei valori din acest vector. Astfel putem obtine costul $O(log(N))$ pe fiecare din cele doua operatii folosind structura de date numita arbori de intervale. Pentru determinarea eficienta a celui mai apropiat stramos comun si pentru detalii despre arborii de intervale consultati bibliografia.

Astfel, s-a construit vectorul $seq[]$ care are urmatoarea proprietate: &#34;daca $&#916; = &#8721; seq[i]$, $firstPos[x] <= i <= firstPos[y]$, x fiind un stramos al lui y, atunci &#916; reprezinta $&#8721; value[u]$, $u &#8712; P$, $P = (x{~0~}, x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y&#34;$. Conform acesteia, daca vom determina cel mai apropiat stramos comun dintre doua noduri, atunci nu va fi nevoie decat de o structura de date ce permite calcularea intr-un mod eficient a sumei pe un interval din $seq[]$ si modificarea unei valori din acest vector. Putem obtine complexitatea $O(log(N))$ pe fiecare din cele doua operatii folosind structura de date numita arbori de intervale. Pentru determinarea eficienta a celui mai apropiat stramos comun si pentru detalii despre arborii de intervale consultati bibliografia.

h2. Enunt