== include(page="template/taskheader" task_id="craciun") ==

Tanaka a decis să sărbătorească crăciunul (cam devreme după orânduirea tradiţională, dar cine poate rezista unui cozonac bun?), şi ca urmare va trebui să îşi achiziţioneze un arbore de crăciun. Din nefericire, arborăria din sătucul său nu are decăt un singur arbore înrădăcinat, cu $N$ noduri. Rădăcina este nodul $1$. Tanaka n-ar vrea să îl cumpere pe tot, dar seful arborăriei îi face o promoţie spectaculoasă: Tanaka va avea voie să cumpere oricare submultime conexa de noduri ale arborelui. Aparatul care va tăia arborele va folosi un cost proporţional cu numărul maxim de noduri dintr-un drum "în sus" (definit riguros în precizări) din multime. Mai mult, din fiecare nod al arborelui pot atarna un numar de $globuri ornamentale$. Tanaka ar vrea să aleaga o multime de care poate atarna cat mai multe $globuri ornamentale$, dar îi pasă şi de cost. Ajutaţi-l pe Tanaka să selecteze o multime unde raportul dintre suma numarului de $globuri ornamentale$ care pot fi atarnate in nodurile acestuia, şi costul pentru a îl cumpăra, să fie maxim.

Tanaka a decis să sărbătorească crăciunul (cam devreme după orânduirea tradiţională, dar cine poate rezista unui kurtos kalacs bun?), şi ca urmare va trebui să îşi achiziţioneze un arbore de crăciun. Din nefericire, arborăria din sătucul său nu are decăt un singur arbore înrădăcinat, cu $N$ noduri. Rădăcina este nodul $1$. Tanaka n-ar vrea să îl cumpere pe tot, dar patronul arborăriei îi face o promoţie spectaculoasă: Tanaka va avea voie să cumpere oricare submultime conexa de noduri ale arborelui. Aparatul care va tăia arborele va folosi un cost proporţional cu numărul maxim de noduri dintr-un drum "în sus" (definit riguros în precizări) din multime. Mai mult, din fiecare nod al arborelui pot atarna un numar de $globuri ornamentale$. Tanaka ar vrea să aleaga o multime de care poate atarna cat mai multe $globuri ornamentale$, dar îi pasă şi de cost. Ajutaţi-l pe Tanaka să selecteze o multime unde raportul dintre suma numarului de $globuri ornamentale$ care pot fi atarnate in nodurile acestuia, şi costul pentru a îl cumpăra, să fie maxim.

h2. Date de intrare