Tehnica liniarizarii arborelui nu ne este de folos, deoarece modul de reprezentare a informatiilor nu permite obtinerea unei complexitati mai bune fata de solutia brute force prezentata mai sus.

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:

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;
# 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$;