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 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 = \max \{value[u]\ /\ u \in P \} </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 = Maxim\{value[u]\ /\ u \in P \} </tex>)

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

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

O imbunatatire la solutia 'precedenta':tree-decompositions#solutie-log-sqrt o reprezinta $heavy path decomposition$, care se foloseste de acelasi algoritm, cu exceptia faptului ca fiul ales pentru determinarea unui lant este cel cu numar maxim de noduri in subarborele sau ({$heavy$}), si nu cel cu inaltimea maxima ({$longest$}). Prin urmare, numarul maxim de lanturi prin care se trece pentru a ajunge de la un nod la radacina este cel mult $O(log(N))$ dupa cum se poate vedea si din figura urmatoare:

O imbunatatire la solutia 'precedenta':tree-decompositions#solutie-log-sqrt o reprezinta $heavy path decomposition$, care se foloseste de acelasi algoritm, cu exceptia faptului ca fiul ales pentru determinarea unui lant este cel cu numar maxim de noduri in subarborele sau ($heavy$), si nu cel cu inaltimea maxima ($longest$). Prin urmare, numarul maxim de lanturi prin care se trece pentru a ajunge de la un nod la radacina este cel mult $O(log(N))$ dupa cum se poate vedea si din figura urmatoare:

p=. !tree-decompositions?Figura3.jpg!
p=. _Fig. 3: Fiecare nod apartine unui singur lant. Lanturile sunt reprezentate de muchii solide._

Complexitatea finala: $O(M*log^2^(N))$. In practica, aceasta tehnica se comporta foarte bine si poate fi folosita cu succes. Singurul inconvenient este numarul mare de linii de cod scrise.

Complexitatea finala: $O(M log^2^(N))$. In practica, aceasta tehnica se comporta foarte bine si poate fi folosita cu succes. Singurul inconvenient este numarul mare de linii de cod scrise.

h2(#aplicatii). Aplicatii