p1096 Color a tree

[•mariusdrg]

Poate cineva sa ma ajute in legatura cu problema asta?
http://acm.tju.edu.cn/toj/showp1096.html
Macar un hint.
Mersi anticipat.

[•Cosmin]

Cred ca poti sa gandesti invers problema. Ce nod il colorezi ultimul? Probabil o frunza. Care frunza? Daca ai de ales intre 2, minimizezi suma colorand-o pe cea de pondere mai mica ultima. Deci practic tai frunze din arbore si ai o coada de prioritati in care tii frunzele curente ordonate dupa ponderea lor.

[•domino]

Solutia pe care am facut-o eu era ceva de genul asta: pentru fiecare subarbore tineam ordinea in care se coloreaza nodurile si faceam un DF. Cand eram intr-un nod apelam recursiv pentru fiecare subarbore si apoi interclasam listele ca sa obtin lista pentru nodul respectiv. Ca sa interclasez doua liste foloseam o dinamica simpla. Complexitate e cam mare, dar intra in timp.

[•Cosmin]

si nu merge mai simplu ce am zis eu? pare corect.

[•sima_cotizo]

Si mie mi se pare corect, dar iau WA.

[•mariusdrg]

Pai nu prea e buna solutia lui cosmin, ca defapt solutia inverseaza problema... nu sti exact ce ti se deblocheaza cand elimini o frunza... ca sa exemplific consider urmatorul test:
4 1 (4 noduri si 1 este radacina)
10 2 5 4(valorile)
1 2
2 3
1 4
Algoritmul lui Cosmin va face urmatoarele:  elimina nodul 4,elimina nodul 3, elimina nodul 2 , elimina radacina, astea in ordine invers cronologica, insumand 4 * 4 + 5 * 3 + 2 * 2 + 10 = 45.(Eu ma refer in ordine inversa fiindca asa merge si algoritmul, defapt logic se coloreaza radacina, dupa aia nodul 2 , dupa nodul 5 si dupa nodul 4.)
solutia optima e sa se elimine nodul 3, elimina nodul 2, elimina nodul 4 si elimina radacina, insumand la 5 * 4 + 2 * 3 + 4 * 2 + 10 = 44. 

[•devilkind]

marius, cred ca cosmin se referea la faptul ca la fiecare pas tai o frunza din arbore. E clar ca la pasul urmator ti se deblocheaza parintele lui. Singura problema care eu nu am inteles-o este cum alege la un pas frunza care o taie.

[•mariusdrg]

Pai nu e neaparat sa se deblocheze parintele ca un parinte poate avea mai multi fi si unul din fi poate sa fie chiar celalalta frunza, cum este cazul dat de mine... in acest caz nu se deblocheaza nimic cand elimini 4-le.

[•devilkind]

da corect, deblochezi un nod de abia dupa ce ai taiat toti fii lui.