p=. !tree-decompositions?fig1.jpg!

p=. _Fig. 1: Pentru arborele din figura de mai sus si vectorul de valori_ <tex> value[\ ] = \{3, 5, 7, 1, 2, 4\} </tex>, <tex> seq[\ ] </tex> _construit este ilustrat in figura. Se observa usor ca tot subarborele unui nod se anuleaza cand este explorat in intregime._

p=. _Fig. 1: Pentru arborele de mai sus si vectorul de valori_ <tex> value[\ ] = \{3, 5, 7, 1, 2, 4\} </tex>, <tex> seq[\ ] </tex> _construit este ilustrat in figura. Se observa usor ca tot subarborele unui nod se anuleaza cand este explorat in intregime._

Astfel, s-a construit vectorul <tex> seq[\ ] </tex> care are urmatoarea proprietate: "daca <tex> \Delta = \displaystyle\sum_{i = firstPos[x]}^{firstPos[y]} seq[i] </tex>, <tex> x </tex> fiind un stramos al lui <tex> y </tex>, atunci <tex> \Delta </tex> reprezinta <tex> \Delta = \displaystyle\sum_{u \in P} value[u] </tex>, <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}) </tex>, <tex> x_{0} = x </tex>, <tex> x_{n} = y </tex>". 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 <tex> seq[\ ] </tex> 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':tree-decompositions#bibliografie.

S-a construit, astfel, vectorul <tex> seq[\ ] </tex> care are urmatoarea proprietate: "daca <tex> \Delta = \displaystyle\sum_{i = firstPos[x]}^{firstPos[y]} seq[i] </tex>, <tex> x </tex> fiind un stramos al lui <tex> y </tex>, atunci <tex> \Delta = \displaystyle\sum_{u \in P} value[u] </tex>, <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}) </tex>, <tex> x_{0} = x </tex>, <tex> x_{n} = y </tex>". Conform acesteia, daca vom determina cel mai apropiat stramos comun pentru 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 <tex> seq[\ ] </tex> 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':tree-decompositions#bibliografie.

h2(#descompunere-in-lanturi). Descompunere in lanturi

Acum ne vom concentra asupra urmatoarei sarcini, de determinare a valorii de maxim/minim. Sa urmarim enuntul de mai jos.

Acum ne vom concentra asupra urmatoarei sarcini, de determinare a valorii maxime / minime. Sa urmarim enuntul de mai jos.

Fie <tex> G = (V, E) </tex> un graf neorientat conex, <tex> |E| = |V| - 1 </tex> (tot un arbore). Vom considera, bineinteles, ca fiecare nod <tex> x \in V </tex> are asociata o valoare <tex> value[x] </tex> din multimea numerelor reale. Se dau $M$ instructiuni, $M &le; 200000$, de doua tipuri:

* primul tip cere sa se scrie maximul dintre valorile nodurilor ce se afla pe lantul dintre <tex> x, y \in V </tex> (daca <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}), x_{0} = x, x_{n} = y </tex>,  atunci se cere <tex> \Delta = \displaystyle Maxim_{u \in P} value[u] </tex>)

* primul tip de instructiuni cere sa se scrie maximul dintre valorile nodurilor ce se afla pe lantul dintre <tex> x, y \in V </tex> (daca <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}), x_{0} = x, x_{n} = y </tex>,  atunci se cere <tex> \Delta = \displaystyle\max\{value[u]\ /\ u \in P \} </tex>)

* al doilea tip modifica valoarea asociata unui nod.
h3(#solutie-brute). Solutie $O(M*N)$

Sunt o multitudine de solutii simple ce ne pot trece prin minte. Pentru cea aleasa de mine voi retine un vector <tex> parent[\ ] </tex> semnificand parintele unui nod calculat printr-un $depth-search$, si un vector <tex> depth[\ ] </tex> ce retine adancimea, adica numarul de muchii de la radacina pana la nodul interogat. Cu ajutorul lor, prima cerinta se rezolva in $O(N)$ astfel: merg "in sus" in arbore pana cand ajung in cel mai apropiat stramos comun, retinand pe parcurs valoarea maxima ceruta. Rezolvarea cerintei a doua se face simplu in $O(1)$ modificand direct <tex> value[\ ] </tex>.

Sunt o multitudine de solutii simple ce ne pot trece prin minte. Pentru cea aleasa de mine voi retine un vector <tex> parent[\ ] </tex>, semnificand parintele unui nod calculat printr-o parcurgere in adancime, si un vector <tex> depth[\ ] </tex> ce retine adancimea, adica numarul de muchii de la radacina pana la nodul interogat. Cu ajutorul lor, prima cerinta se rezolva in $O(N)$ astfel: merg "in sus" in arbore pana cand ajung in cel mai apropiat stramos comun, retinand pe parcurs valoarea maxima ceruta. Rezolvarea cerintei a doua se face simplu in $O(1)$, modificand direct <tex> value[\ ] </tex>.

h3(#solutie-log-sqrt). Solutie $O(M*log(N)*sqrt(N))$

h2(#aplicatii). Aplicatii
* "Query on a tree":http://www.spoj.pl/problems/QTREE/

* "Caves and tunnels":http://acm.timus.ru/problem.aspx?space=1&num=1553 - Petrozavodsk training camp, September, 2007
* "Delay":problema/delay - Lotul national de informatica, 2002

* "Caves and tunnels":http://acm.timus.ru/problem.aspx?space=1&num=1553 - Petrozavodsk training camp, 2007
* "Delay":problema/delay - Lotul National de Informatica, 2002

* "Omizi":problema/omizi - .campion, 2005

* "Arbfind":problema/arbfind - Lotul national de informatica, 2006

* "Arbfind":problema/arbfind - Lotul National de Informatica, 2006

* "CT":problema/ct - Happy Coding, 2006
h2(#bibliografie). Bibliografie