Fişierul intrare/ieşire:craciun.in, craciun.outSursăAlgoritmiada 2018 Runda Maraton
AutorTamio-Vesa NakajimaAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test4 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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.incraciun.out
3
100 101 102
1 1
151.5

Explicaţie

Se selectează întreg arborele

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?