In continuare voi prezenta enuntul unui tip de problema ce a aparut in fiecare an la concursurile de informatica. Motivul pentru care am ales acest lucru este ca multi ar fi tentati, prin diverse metode si astfel cu mult timp pierdut, sa incerce sa adapteze rezolvarea acesteia la rezolvarea problemei ce necesita _heavy path decomposition_. Iata enuntul:

Fie G = (V, E) un graf neorientat conex, |E| = |V| - 1. Astfel, intre oricare doua noduri x, y apartinand V exista un singur lant ce le uneste. Vom considera ca fiecare nod x din V are asociata o valoare _value[x]_ din multimea numerelor reale. Sa consideram urmatorul enunt.

Fie $G = (V, E)$ un graf neorientat conex, $|E| = |V| - 1$. Vom considera 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 afiseze suma valorilor tuturor nodurilor ce se afla pe lantul dintre $x, y &#8712; V$ (practic, daca $P = (x{~0~},x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y$, este lantul elementar ce uneste cele doua noduri, atunci se cere $&#916; = &#8721; value[i]$, $u &#8712; P$), iar al doilea tip modifica valoarea atasata unui nod.

_Se dau M instructiuni, M <= 100000, de doua tipuri : primul tip cere sa se afiseze suma valorilor tuturor nodurilor ce se afla pe lantul dintre x, y din V (practic, daca P = (x{~0~},x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y, este lantul elementar ce uneste cele doua noduri, atunci se cere S = _Suma dupa value[u]_, u apartine P), iar al doilea tip modifica valoarea atasata unui nod._

h2. Solutia $O((M+N)log(N))$

Solutia se foloseste de o tehnica utilizata destul de frecvent in concursurile de informatica : liniarizarea arborelui. Aceasta presupune o parcurgere in adancime si retinerea unor informatii necesare pentru interogare si actualizare: seq[], firstPos[], lastPos[]. Iata pseudocodul acestei parcurgeri :

Solutia se foloseste de o tehnica utilizata destul de frecvent in concursurile de informatica : liniarizarea arborelui. Aceasta presupune o parcurgere in adancime si retinerea unor informatii necesare pentru interogare si actualizare: $seq[]$, $firstPos[]$, $lastPos[]$. Iata pseudocodul acestei parcurgeri :

== code(c) |
PARCURGE(x)

    lastPos[x] = seq_len;
==

_Fig. 1: Pentru arborele din figura alatura si vectorul de valori value[] = {3, 5, 7, 1, 2, 4} vectorul seq[] construit este ilustrat mai jos. Se observa usor ca tot subarborele unui nod se anuleaza cand este explorat in intregime._

_Fig. 1: Pentru arborele din figura alatura si vectorul de valori $value[] = {3, 5, 7, 1, 2, 4}$, $seq[]$ construit este ilustrat mai jos. Se observa usor ca tot subarborele unui nod se anuleaza cand este explorat in intregime._

p=. !heavy-path-decomposition?Figura1.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 un cost cat mai mic pentru calcularea eficienta a sumei pe un interval si modificarea unei valori din acest vector $seq[]$. Cu ajutorul structurii de date numita arbori de intervale putem obtine costul $O(log(N))$ pe fiecare din cele doua operatii. Pentru determinarea eficienta a celui mai apropiat stramos comun consultati bibliografia.