Voi prezenta intr-un mod indirect cum se ajunge la aceasta complexitate, intrucat exista o solutie relativ asemanatoare celei pe care mi-am propus sa o prezint, insa nu la fel de rapida, numita _longest path decomposition_. Si, desigur, nu este rau daca stim ceva in plus. :)

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

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: