Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | halftree.in, halftree.out | Sursă | InfoPro, Runda 3, Grupa A |
| Autor | Bogdan Sitaru | Adăugată de |  Bogdan Sitaru •bogdan10bos |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Halftree
Pasionat de problemele cu arbori, Petrică a găsit următoarea problemă: Se dă un arbore cu N noduri şi costuri pare pe muchii.
Distanţa dintre două noduri ale arborelui este egală cu suma costurilor muchiilor de pe cel mai scurt drum dintre cele două noduri.
Se defineşte valoarea unui arbore ca fiind suma distanţelor dintre oricare 2 noduri ale acestuia.
Petrică are la dispoziţie următoarea operaţie, pe care o poate face o singură dată: alege un lanţ al arborelui şi înjumătăţeşte costul tuturor muchiilor de pe acel lanţ. Ajutaţi-l să găsească cea mai mică valoare a unui arbore obţinut după aplicarea operaţiei.
Un lanţ se defineşte ca fiind o înşiruire de noduri distincte 
(pentru 
), unde există o muchie între 
şi 
pentru orice 
.
Date de intrare
Fişierul de intrare halftree.in conţine pe primul rând se gaseşte un număr întreg pozitiv N reprezentând numărul de noduri ale arborelui.
A doua linie conţine N-1 numere întregi 
, reprezentând că există o muchie între nodul i şi nodul p_i.
A treia linie conţine N-1 numere întregi 
, unde c_i reprezintă costul muchiei dintre i şi p_i.
Date de ieşire
În fişierul de ieşire halftree.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| halftree.in | halftree.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
