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':job_detail/608824?action=view-source 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
