Insa, cu _longest path_decomposition_, tehnica ce necesita cunostine minime despre grafuri, vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:

# Elimina cel mai lung lant radacina-frunza din arbore si apeleaza recursiv pentru restul componentelor conexe;

# Elimina cel mai lung lant radacina-frunza din arbore si apeleaza recursiv pentru restul componentelor conexe ;

# Retine fiecare lant ca un vector $Path[].array[]$ cu noduri ordonate crescator dupa adancime si pastreaza un pointer catre nodul din lantul sau parinte $Path[].parent$;
# Pentru fiecare nod retine lantul caruia apartine $whatPath[]$ si pozitia in vectorul lantului $whatPos[]$.