Ioi da mahh .  ups.

Cum se putea lua 5 puncte la problema Cezar? Ca vad ca multi o luat punctaje cu 5 in capat. Poti sa iei numa jumate de test sau cum?

"O implementare posibilă utilizează metoda GREEDY, O(n*(n-k)) sau O((n-k)*log(n))

Se elimină succesiv, dintre frunzele existente la un moment dat, frunza de cost minim. Toate nodurile au costul iniţial 1. La eliminarea unei frunze, se incrementează cu 1 costul tatălui acesteia. Validitatea metodei rezultă din observaţia că, la eliminarea unei frunze oarecare, tatăl acesteia poate deveni frunză la rândul lui, dar cu un cost strict mai mare decât al frunzei eliminate.

Se poate reţine arborele cu ajutorul listelor de adiacenţă (liniare sau organizate ca arbori de căutare), iar frunzele se pot memora într-un minheap de costuri, structură care se actualizează în timp logaritmic." 
   Asta ii solutia oficiala la Cezar. Perfect logic asai??  Is curios cine so fi gandit sa o faca asa . Ca de obicei era o rezolvare prea simpla sa te gandesti la ea. Inca un 0 la lista ea de punctaje speciale la OJI.

nush sigur dak merge dar e o idee. Faci un DF si ptr fiecare nod retii cate noduri are subarborele care il are ca radacina. Apoi iei si bagi toti vecinii radacinii intr-o coada si iei maximu de acolo (sa zicem x), si pui strada r-x (r e radacina). Scoti elementu respectiv din coada si bagi vecinii lui si repeti algoritmu de k ori. (atentie cand bagi cate o muchie nu pui de fiecare data de la radacina la nod  muchie ci de la nod la tatal sau). Sper ca ai inteles ce am zis si sper sa fie bine
[later edit] de fapt asta merge doar dak ai radacina fixata dar akuma am observat ca tot tu sa o determini deci nu merge

Ma gandeam io ca ii ceva cu numarul de noduri al subarborelor, da desteptu de mine nu m-am gandit la o coada  .Pacat ca nu primim punctaje partiale pentru aflarea radacini ca aia era simpla. Parcurgeai cu BF dintr-un nod (1) si faceai media distantelor  de la nodul 1 la celelalte noduri si atunci radacina era situata la distanta medie fatza de 1 .

Cineva cu inima buna  sa imi zica si mie cum ar fi trebuit sa fac problema 2 de la 11-12(Cezar) ca mi-ma batut capu 3 ore la Oji 2007 si nu am reusit sa o rezolv.
      http://olimpiada.info/oji2007/probleme/subiecte_oji_2007.zip
    PS Daka stiti  formula de la problema 1  sa imi scrieti cum ati ajuns la ea va rog.