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.
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':job_detail/608822?action=view-source 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, pentru un nod $x$ pentru care am apelat in prealabil functia $DF$ pentru toti fiii sai, avem urmatoarele cazuri:
# 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. Pentru fiecare nod $x$ vom retine $poz{~x~}$, pozitia sa in lantul de care apartine. Acum o operatie de update $(0, x, y)$ va putea fi efectuata in $O(log N)$, actualizand arborele de intervale asociat lantului care contine nodul $x$. Un query $(1, x, y)$ se va rezolva astfel: daca $x$ si $y$ apartin aceluiasi lant, interogam pentru acesta intervalul $[min(poz{~x~}, poz{~y~}), max(poz{~x~}, poz{~y~})]$ si actualizam solutia curenta daca este cazul. Altfel, daca parintele lantului lui $x$ are nivelul mai mic decat parintele lantului lui $y$, interschimbam pe $x$ si $y$. Vom interoga, pentru lantul lui $x$, intervalul $[1, poz{~x~}]$, $x$ primeste valoarea parintele lantului lui $x$ si reluam algoritmul pentru noua pereche $(x, y)$. Complexitatea finala $O(√N * log N)$ pentru un query se datoreaza faptului ca drumul dintre $x$, respectiv $y$ si $LCA (x, y)$ va traversa maxim $√N$ lanturi, aceasta proprietate datorandu-se modului de constructie al lanturilor. Aceasta solutie ar trebui sa obtina $60$ de puncte.
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. Pentru fiecare nod $x$ vom retine $poz{~x~}$, pozitia sa in lantul de care apartine. Acum o operatie de update $(0, x, y)$ va putea fi efectuata in $O(log N)$, actualizand arborele de intervale asociat lantului care contine nodul $x$. Un query $(1, x, y)$ se va rezolva astfel: daca $x$ si $y$ apartin aceluiasi lant, interogam pentru acesta intervalul $[min(poz{~x~}, poz{~y~}), max(poz{~x~}, poz{~y~})]$ si actualizam solutia curenta daca este cazul. Altfel, daca parintele lantului lui $x$ are nivelul mai mic decat parintele lantului lui $y$, interschimbam pe $x$ si $y$. Vom interoga, pentru lantul lui $x$, intervalul $[1, poz{~x~}]$, $x$ primeste valoarea parintele lantului lui $x$ si reluam algoritmul pentru noua pereche $(x, y)$. Complexitatea finala $O(√N * log N)$ pentru un query se datoreaza faptului ca drumul dintre $x$, respectiv $y$ si $LCA (x, y)$ va traversa maxim $√N$ lanturi, aceasta proprietate datorandu-se modului de constructie al lanturilor. Aceasta 'solutie':job_detail/608823?action=view-source ar trebui sa obtina $60$ de puncte.
Pentru a reduce complexitatea la $O(N * log^2^ N)$, vom construi lanturile diferit, modificand abordarea in cazul $2$ al DF-ului. Astfel, in loc sa unim un nod $x$ cu cel mai lung lant care se termina intr-unul din fiii sai, il vom uni cu lantul asociat fiului care cuprinde cele mai multe noduri in subarborele sau. Aceasta modalitate garanteaza ca drumul dintre $x$, respectiv $y$ si $LCA (x, y)$ va traversa maxim $log N$ lanturi. Aceasta solutie obtine $100$ de puncte.
Pentru a reduce complexitatea la $O(M * log^2^ N)$, vom construi lanturile diferit, modificand abordarea in cazul $2$ al DF-ului. Astfel, in loc sa unim un nod $x$ cu cel mai lung lant care se termina intr-unul din fiii sai, il vom uni cu lantul asociat fiului care cuprinde cele mai multe noduri in subarborele sau. Aceasta modalitate garanteaza ca drumul dintre $x$, respectiv $y$ si $LCA (x, y)$ va traversa maxim $log N$ lanturi. Aceasta 'solutie':job_detail/608824?action=view-source obtine $100$ de puncte.
Precedentele doua abordari poarta numele de Longest Path Decomposition, respectiv Heavy Path Decomposition, ambele fiind tratate in acest 'articol':problema/tree-decompositions.
Precedentele doua abordari poarta numele de Longest Path Decomposition, respectiv Heavy Path Decomposition, ambele fiind tratate in acest 'articol':tree-decompositions.
h3. Probleme propuse
* 'Query on a Tree':http://www.spoj.pl/problems/QTREE/
* 'Caves and Tunnels$http://acm.timus.ru/problem.aspx?space=1&num=1553
@admini: mai stiti vreuna? :)
* 'Caves and Tunnels':http://acm.timus.ru/problem.aspx?space=1&num=1553
== include(page="template/taskfooter" task_id="heavypath") ==
