457 Maimute

[•filipb]

Aici puteţi discuta despre problema Maimute.

[•crawler]

Pe urmatoarele N-1 linii se vor afla cate 2 numere X si Y reprezentand faptul ca intre maimuta X si Y exista o relatie directa

nu cred ca am inteles bine, relatia aia este X este tatal lui Y sau Y este tatal lui X ?

[•devilkind]

poate fi ori una ori cealalta, nu are importanta.

[•Mishu91]

Daca de exemplu intre 1 si 2, si 1 si 3 exista o relatie de rudenie, se poate ca si intre 2 si 3 sa existe o relatie de rudenie?

[•devilkind]

arborele genealogic al familiei acestora

Deci nu.

[•Mishu91]

Mersi 

[•vladiana]

Am facut un LCA cu arbore de intervale.....prima data rulez un df si stabilesc adancimile si una dintre pozitile pe care apare fiecare nod. Apoi fac un update pe arbore iar apoi fiecare interogare in O(log N)......stie cineva cumva dc iau 4 TLE si ma poate ajuta? compl finala ar fii: O(2*n + log n * (m + n))

[•cos_min]

Se poate face o singura parcurgere, dupa care sa raspunzi in O(1) pt fiecare intrebare.

[•vladiana]

si in parcurgere ce aflu si cum rasp in O(1) ?

[•Marius]

Nu stiu problema, dar iti pot spune ca poti raspunde la LCA in O(1) cu hashuri cu o preprocesare in O(N log*N) cu multimi disjuncte.

[•devilkind]

Exista o solutie mai simpla. Complexitatea oficiala e O(N+M). Gandestete daca nu te poate ajuta intrun fel acea parcurgere euler.

[•vladiana]

nu prea imi vine in cap decat daca unul dintre cele 2 noduri se afla intre 2 aparitii ale celuilalt nod in parcurgerea euler 

[•pauldb]

Exact. Si pentru ce iti trebuie LCA atunci?

[•Bit_Master]

O maimuta poate avea mai multi parinti?

[•pauldb]

Nu.

[•deneo]

cred ca ar trebui marit un pic timpul de executie
http://infoarena.ro/job_detail/631524