Lant maxim in arbore

[•nparfene2004]

La multi ani tuturor!

V-as ruga sa ma ajutati la urmatoarea problema: Fie un arbore (graf conex fara cicluri). Sa se determine un lant elementar de lungime maxima.

Daca as face un BF din fiecare nod, as avea o complexitate O(n x (n + m)). As putea reduce poate ceva daca fac BF numai din noduri terminale. Intrebarea mea este: exista un algoritm mai bun?
Multumesc!

[•vendetta]

Da, este. Se poate in (n + m). Cred ca problema aceasta cere acelasi lucru.

[•klamathix]

Cea mai evidenta solutie e o dinamica dp[nod] = cel mai lung lant in jos pornind din nod. Evident in fiecare nod ai sa incerci apoi sa unesti fii cu dp maxim.

Alta solutie mai simpla ar fi sa faci un DF. Vei obtine un nod X, cu distanta cea mai mare de radacina. Daca mai faci un df din X si nodul cu cea mai mare distanta fata de el este Y, atunci X - Y este un lant de lungime maxima.

[•nparfene2004]

Multumesc pentru sfaturi!
Mi se pare interesanta ideea cu exact doua DF-uri, desi nu-mi dau seama cum se arata (macar intuitiv) corectitudinea algoritmului.

[•wefgef]

Hint: Trebuie sa demonstrezi ca oricare ar fi un nod X din arbore, cea mai departata frunza de X va face parte intotdeauna dintr-un lant de lungime maxima. Se face prin reducere la absurd.