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:
* agatam arborele intr-un nod oarecare si obtinem un arbore cu radacina

* pentru fiecare nod precalculam {$dist{~i~}$}, reprezentand distanta sa pana la radacina

* pentru fiecare nod $i$ precalculam {$dist{~i~}$}, reprezentand distanta sa pana la radacina

* precalculam cele necesare pentru algoritmul de _Lowest Common Ancestor_

* raspundem la intrebari de forma {$d{~i,j~}$} prin {$dist{~i~} + dist{~j~} - dist{~lca{~i,j~}~}$}

* distanta dintre doua noduri oarecare $i$ si $j$ va fi egala cu {$dist{~i~} + dist{~j~} - dist{~lca(i,j)~}$}

h2. Mod de calcul

* daca are fii atunci il punem la inceput, la sfarsit si intre parcurgerile euler ale fiilor
Cand facem aceasta parcurgere retinem de asemenea si urmatoarele informatii suplimentare:

* adancimea fiecarui nod din parcurgere, obtinand un sir de adancimi
* una din pozitiile pe care fiecare nod apare in parcurgere

Pentru perechea de noduri ({$4, 3$}), avem {$lca(4, 3)$} egal cu nodul care se gaseste intre {$poz{~4~}$} si {$poz{~3~}$} in parcurgerea euler si are adancimea minima. Acest nod este $1$, deci {$lca(4, 3) = 1$}.

Am redus problema la aflarea minimului intre doua pozitii ale unui sir (_Range Minimum Query_). Aceasta subproblema o putem rezolva optim folosind arbori de intervale, sau o metoda folosind spatiu supraliniar ({$Nlog{~2~}N$}) a minimelor pe intervale de puteri ale lui {$2$}, incepand de la pozitia {~i~}. Timpul de preprocesare este {~O(N)~} pentru arbori de intervale si {$O(Nlog{~2~}N)$} pentru a doua metoda. In ambele variante timpul de interogare este {$O(log{~2~}N)$}.
Vom prezenta in continuare metoda cu spatiu supraliniar. Calculam minimele inductiv, pastrand {$min{~i,k~}$} = minimul pe intervalul {$[i...i + 2^k^ - 1]$} (de lungime {$2{^k^}$}), si {$minpos{~i,k~}$} = pozitia minimului de pe intervalul {$[i...i + 2^k^ - 1]$}. Acest tablou va fi construit recursiv: pentru $k = 0$ avem {$min{~i,0~} = a~i~$} si {$minpos{~i,0~} = i$} si pentru k > 0 avem:
* {$min{~i,k~}$} = minim({$min{~i,k-1~}$}, {$min{~i+2{^k-1^},k-1~}$})

Am redus problema la aflarea minimului intre doua pozitii ale unui sir ({_Range Minimum Query_}). Aceasta subproblema o putem rezolva optim folosind arbori de intervale, sau o metoda folosind spatiu supraliniar ({$Nlog{~2~}N$}) a minimelor pe intervale de puteri ale lui {$2$}, incepand de la pozitia {$i$}. Timpul de preprocesare este {~O(N)~} pentru arbori de intervale si {$O(Nlog{~2~}N)$} pentru a doua metoda. In ambele variante timpul de interogare este {$O(log{~2~}N)$}.
Vom prezenta in continuare metoda cu spatiu supraliniar. Calculam minimele inductiv, pastrand:
 
* {$min{~i,k~}$} = minimul pe intervalul {$[i...i+2^k^-1]$} (de lungime {$2^k^$}), si
* {$minpos{~i,k~}$} = pozitia minimului de pe intervalul {$[i...i+2^k^-1]$}.
 
Acest tablou va fi construit recursiv astfel: pentru $k = 0$ avem {$min{~i,0~} = a{~i~}$} si {$minpos{~i,0~} = i$}, iar pentru k > 0 avem:
 
* {$min{~i,k~}$} = minim({$min{~i,k-1~}$}, {$min{~i+2^k-1^,k-1~}$})

* {$minpos{~i,k~}$} = pozitia minimului ({$minpos{~i,k-1~}$} sau {$minpos{~i+2{^k-1^},k-1~}$})
Pentru _query_ intre pozitiile $l$ si $r$ procedam astfel: fie $k$ cel mai mare numar astfel incat {$2^k^$} ≤ lungimea intervalului {$(l, r)$}.

     min(l, r) = minim( min[l][k], min[r * 2^k + 1][k])
     pozmin(l, r) = pozitia minimului

     {$min(l, r)$} = minim( {$min{~l,k~}$}, {$minimul pe intervalul (l+2^k^, r)$})
     {$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)$}.