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 este inapta functionarii, deoarece informatiile pe care le putem retine nu permit obtinerea unei complexitati mai bune.

Tehnica liniarizarii arborelui nu poate functiona, deoarece informatiile pe care le putem retine nu ne pot permite sa obtinem o complexitate mai buna.

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: