seq[seq_len] = value[x]
    firstPos[x] = seq_len

    pentru fiecare fiu y al lui x executa

    pentru fiecare fiu nevizitat y al lui x executa

        PARCURGE(y) // apeleaza recursiv pentru y
    sfarsit pentru

Tehnica liniarizarii arborelui nu ne este de folos in acest caz, deoarece modul de reprezentare a informatiilor nu permite obtinerea unei complexitati mai bune fata de 'solutia lenta':tree-decompositions#solutie-brute prezentata mai sus.

O solutie mai buna foloseste asa numita tehnica $longest path decomposition$, tehnica ce necesita cunostine minime despre grafuri si cu care vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:

O solutie mai buna foloseste asa numita tehnica $longest path decomposition$, tehnica ce necesita cunostinte minime despre grafuri si cu care vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:

# Se elimina cel mai lung lant radacina-frunza din arbore si se apeleaza recursiv pentru restul componentelor conexe;
# Se retine fiecare lant ca un vector <tex> Path[\ ].array[\ ] </tex> cu noduri ordonate crescator dupa adancime si se pastreaza un pointer catre nodul din lantul sau parinte <tex> Path[\ ].parent </tex>;

* Emilian Miron - "_Lowest Common Ancestor_":lowest-common-ancestor
* Michael A. Bender, Martin Farach-Colton - "_The level ancestor problem simplified_":http://cs.sunysb.edu/~bender/pub/latin02-level.ps
* Oren Weimann - "_Advanced data structures_":http://courses.csail.mit.edu/6.851/spring07/scribe/lec09.pdf

 
h2. Discutii pe forum

2578

3694