Acum ne vom concentra asupra urmatoarei sarcini, de determinare a valorii de maxim/minim. 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 <= 200000$, de doua tipuri:

Fie $G = (V, E)$ un graf neorientat conex, $|E| = |V| - 1$ (yup, tot arbore). 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 <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 cere sa se scrie maximul dintre valorile nodurilor ce se afla pe lantul dintre $x, y ∈ V$ (daca $P = (x{~0~},x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y$,  atunci se cere $Δ = Maxim {value[u] | u ∈ P}$)

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