Fişierul intrare/ieşire:halftree.in, halftree.outSursăInfoPro, Runda 3, Grupa A
AutorBogdan SitaruAdăugată debogdan10bosBogdan Sitaru bogdan10bos
Timp execuţie pe test0.25 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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 a_1, a_2, \dots, a_K (pentru K \ge 1), unde există o muchie între a_i şi a_{i+1} pentru orice 1 \le i < K.

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 p_2, p_3, \dots, p_N, reprezentând că există o muchie între nodul i şi nodul p_i.
A treia linie conţine N-1 numere întregi c_2, c_3, \dots, c_N, unde c_i reprezintă costul muchiei dintre i şi p_i.

Date de ieşire

În fişierul de ieşire halftree.out se va afişa pe primul rând un număr întreg reprezentând valoarea minimă a unui arbore obţinută după aplicarea operaţiei asupra arborelui iniţial.

Restricţii

  • 1 \le N \le 10^5
  • 1 \le p_i < i pentru orice i de la 2 la N
  • -10^3 \le c_i \le 10^3 pentru orice i de la 2 la N
  • c_i este par pentru orice i de la 2 la N
  • Subtask 1: Arborele nu conţine niciun nod cu grad mai mare de 2 (arborele este un lanţ).
  • Subtask 2: 1 \le N \le 10^2 si 0 \le c_i \le 10^3 pentru orice i de la 2 la N
  • Subtask 3: 1 \le N \le 10^3 si 0 \le c_i \le 10^3 pentru orice i de la 2 la N
  • Subtask 4: si 0 \le c_i \le 10^3 pentru orice i de la 2 la N
  • Subtask 5: Toate valorile muchiilor sunt egale (c_i = c_j pentru orice 2 \le i, j \le N).
  • Subtask 6: 1 \le N \le 10^3
  • Subtask 7: Fără restricţii suplimentare

Exemplu

halftree.inhalftree.out
5
1 1 2 1
30 16 38 14
254
10
1 1 2 2 3 3 7 7 9
-2 2 -4 4 -6 6 10 2 0
77
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?