h2. Enunt

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:

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[u]$, $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, 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)$

 
Sunt o multitudine de solutii simple ce ne pot trece prin minte. Pentru cea aleasa de mine voi retine un vector $parent[]$ semnificand parintele unui nod calculat printr-un breath-search, si $depth[]$ ce arata adancimea, adica numarul de muchii de la radacina pana la nodul interogat. Cu ajutorul lor, urmatorul pseudocod rezolva primul tip de cerinta:
 
== code(c) |
QUERY(x, y)
    ret = Maxim(value[x], value[y]);
    cat timp x diferit de y executa
        daca depth[x] > depth[y] atunci
            x = parent[x];
            ret = Maxim(ret, value[x]);
        altfel
            y = parent[y];
            ret = Maxim(ret, value[y]);
        sfarsit daca
    sfarsit cat timp
    returneaza ret;
==
 
Rezolvarea cerintei a doua se face simplu in $O(1)$.
 
h2. Solutia $O(M*log^2^(N))$
 
Voi prezenta intr-un mod indirect cum se ajunge la aceasta complexitate, intrucat exista o solutie relativ asemanatoare celei pe care mi-am propus sa o prezint, insa nu la fel de rapida, numita _longest path decomposition_.