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.

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