h2. Enunt

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:

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 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.

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.

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 numita 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)