5
|

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$.
 
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:
 
== 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
==

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