In continuare voi prezenta enuntul unui tip de problema ce a aparut la multe dintre concursurile de informatica. Motivul pentru care am ales acest lucru este unii participanti pot fi tentati sa incerce sa adapteze rezolvarea acesteia la rezolvarea problemei ce necesita heavy path decomposition. Lucru ce nu este posibil, pierzand astfel timp pretios. Iata enuntul:

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 ce uneste cele doua noduri, atunci se cere $&#916; = &#8721; value[i]$, $u &#8712; P$), iar al doilea tip modifica valoarea atasata unui nod.

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 ce uneste cele doua noduri, atunci se cere $&#916; = &#8721; value[u]$, $u &#8712; P$), iar al doilea tip modifica valoarea atasata unui nod.

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

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.

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.
h2. Enunt
 
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.
 
h2. Solutia $O(M*N)$