h2. Indicatii de rezolvare

Pentru a usura rezolvarea acestei probleme, vom considera ca nodul $1$ este radacina arborelui. De asemenea, definim nivelul unui nod $x$ din arbore ca fiind numarul de noduri din lantul elementar care uneste radacina de nodul $x$. Mai definim parintele unui nod $x$ ca fiind singurul vecin al sau cu nivel mai mic decat al lui $x$.

Pentru a usura rezolvarea acestei probleme, vom considera ca nodul $1$ este radacina arborelui. De asemenea, definim nivelul unui nod $x$ din arbore ca fiind numarul de noduri din lantul elementar care uneste radacina de nodul $x$. Mai definim parintele unui nod $x$ ca fiind singurul vecin al sau cu nivel mai mic decat al lui $x$ si parintele unui lant ca fiind parintele nodului aflat pe nivelul cel mai mic al lantului respectiv.

Cea mai simpla rezolvare, de complexitate $O(N * M)$, va parcurge nod cu nod fiecare lant ce apare la un query, retinand valoarea maxima care apare pe acest drum. Pornind initial cu doi pointeri din nodurile $x$ si $y$, ne vom muta, la fiecare pas, din nodul aflat pe cel mai mare nivel in parintele acestuia, pana cand cei doi pointeri indica spre acelasi nod, 'LCA-ul':problema/lca nodurilor $x$ si $y$. Operatia de update se realizeaza in $O(1)$, inlocuind valoarea veche $v{~x~}$ cu $y$. Aceasta solutie ar trebui sa obtina $20$ de puncte.

Stim ca putem afla maximul dintr-o subsecventa a unui sir cu ajutorul unui 'arbore de intervale':problema/arbint. Urmatoarea solutie se foloseste de aceasta structura pentru a reduce complexitatea la $O(M * √N * log N)$. Nu putem aplica un arbore de intervale pe arborele nostru, astfel ca suntem nevoiti sa il descompunem in lanturi. Aceasta descompunere se poate face cu ajutorul unei parcurgeri 'DF':problema/dfs, astfel:

Stim ca putem afla maximul dintr-o subsecventa a unui sir cu ajutorul unui 'arbore de intervale':problema/arbint. Urmatoarea solutie se foloseste de aceasta structura pentru a reduce complexitatea la $O(M * √N * log N)$. Nu putem aplica un arbore de intervale pe arborele nostru, astfel ca suntem nevoiti sa il descompunem in lanturi. Aceasta descompunere se poate face cu ajutorul unei parcurgeri 'DF':problema/dfs. Astfel, pentru un nod $x$ pentru care am apelat in prealabil functia $DF$ pentru toti fiii sai, avem urmatoarele cazuri:

== code(c) |
QUERY(x, y)
    ret = value[x]
    cat timp x diferit de y executa
        daca whatPath[x] = whatPath[y] atunci
            ret = Maxim(ret, QUERYAi(Path[whatPath[y]], whatPos[x], whatPos[y]))
            y = x
        altfel
            ret = Maxim(ret, QUERYAi(Path[whatPath[y]], 1, whatPos[y]))
            y = Path[whatPath[y]].parent
        sfarsit daca
    sfarsit cat timp
    returneaza ret
==

# Nodul $x$ este o frunza. In acest caz, cream un lant nou care contine doar pe $x$.
# Nodul $x$ este un nod intern. In aceasta situatie, il adaugam pe $x$ la cel mai lung lant care se termina intr-unul din fiii sai.
 
Pentru fiecare lant astfel obtinut vom sorta nodurile crescator dupa nivel, pentru a putea tine un arbore de intervale care va retine in intervalul $[x, y]$ valoarea maxima a unui nod aflat, in lantul care-l contine, intre pozitiile $x$ si $y$, inclusiv. Acum o operatie de update va putea fi efectuata in O(log N), actualizand arborele de intervale asociat lantului care contine nodul a carui valoare se modifica.

== include(page="template/taskfooter" task_id="heavypath") ==