| Fişierul intrare/ieşire: | craciun.in, craciun.out | Sursă | Algoritmiada 2018 Runda Maraton |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Bogdan Ciobanu •bciobanu |
| Timp execuţie pe test | 2 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Craciun
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.
Date de intrare
Prima linie a fişierului de intrare craciun.in va conţine valoarea N.
A doua linie conţine N numere, unde al i-lea număr reprezintă numarul de globuri ornamente ce pot fi atarnate in nodul i.
A treia linie conţine N-1 numere, unde al i-lea număr reprezintă strămoşul nodului i+1.
Date de ieşire
Fişierul de ieşire craciun.out va conţine raportul cerut.
Restricţii şi precizări
- 0 ≤ numarul de globuri ornamentale care pot fi atarnate in fiecare nod ≤ 1.000.000
- Pentru a primi punctajul pe un test, răspunsul vostru trebuie să aibă eroarea relativă sau absolută faţă de răspunsul comisiei de maxim 10-4.
- Nu se va accepta notaţia ştiinţifică în afişarea răspunsului (de exemplu, 1e9 nu e acceptabil).
- Un drum "în sus" reprezintă un drum a1 - a2 - ... - aK unde ai este fiul lui ai+1, pentru i = 1, ..., K-1.
- Subtask 1 (feedback testul 2) - 10 puncte: 1 ≤ N ≤ 500.
- Subtask 2 (feedback testul 7) - 10 puncte: 1 ≤ N ≤ 1.000.
- Subtask 3 (feedback testele 9 si 10) - 10 puncte: 1 ≤ N ≤ 3.000.
- Subtask 4 (feedback testele 13 si 15) - 40 puncte: 1 ≤ N ≤ 50.000.
- Subtask 5 (feedback testele 17 si 18) - 30 puncte: 1 ≤ N ≤ 100.000.
Exemplu
| craciun.in | craciun.out |
|---|---|
| 3 100 101 102 1 1 | 151.5 |
Explicaţie
Se selectează întreg arborele
