Problema luata in discutie este ca, avand un arbore dat, sa putem raspunde rapid la multe intrebari de genul: _"Care este stramosul comun cel mai apropiat dintre doua noduri din arbore?"_.

h2. Exemplu

(toc)*{text-align:center} *Continut*
* 'Exemplu':lca-lowest-common-ancestor#exemplu
* 'Aplicabilitate':lca-lowest-common-ancestor#aplicabilitate
* 'Mod de calcul':lca-lowest-common-ancestor#calcul
 
h2(#exemplu). Exemplu

!LCA-Lowest-common-ancestor?euler.jpg!

* $lca(1,5) = 1$
* $lca(5,3) = 3$

h2. Aplicabilitate

h2(#aplicabilitate). Aplicabilitate

Dandu-se un arbore cu costuri sa se raspunda rapid la intrebari de genul: _"care este distanta minima intre doua noduri date?"_. O solutie pentru problema de fata ar fi:

* precalculam cele necesare pentru algoritmul de _Lowest Common Ancestor_
* distanta dintre doua noduri oarecare $i$ si $j$ va fi egala cu {$dist{~i~} + dist{~j~} - 2*dist{~lca(i,j)~}$}

h2. Mod de calcul

h2(#calcul). Mod de calcul

In prima etapa a algoritmului facem o parcurgere euleriana a arborelui dat. O parcurgere euleriana este o parcurgere a arborelui in ordinea din figura: se parcurg fiii si se intercaleaza intre ei tatal, obtinand o parcurgere continua.

     {$pozmin(l, r)$} = pozitia minimului intre $l$ si $r$
Daca {$l = pos{~i~}$} si {$r = pos{~j~}$} ({$pos{~i~} < pos{~j~}$}) la sfarsitul _query_-ului {$euler{~pozmin~}$} este chiar {$lca(i, j)$}.