Problem 681: 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, ..., a_K$ (pentru $K ≥ 1$ ), unde există o muchie între $a_i$ și $a_{i+1}$ pentru orice $1 ≤ i < K$ .

Date de intrare

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, ..., 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, ..., c_N$ , unde $c_i$ reprezintă costul muchiei dintre $i$ și $p_i$ .

Date de ieșire

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 ≤ N ≤ 10^5$
$1 ≤ p_i < i$ pentru orice $i$ de la $2$ la $N$
$−10^3 ≤ c_i ≤ 10^3$ pentru orice $i$ de la $2$ la $N$
$c_i$ este par pentru orice $i$ de la $2$ la $N$

Subtask 1 (10 puncte)

Arborele nu conține niciun nod cu grad mai mare de $2$ (arborele este un lanț).

Subtask 2 (25 de puncte)

$1 ≤ N ≤ 10^2$
$0 ≤ c_i ≤ 10^3$ pentru orice $i$ de la $2$ la $N$

Subtask 3 (15 puncte)

$1 ≤ N ≤ 10^3$
$0 ≤ c_i ≤ 10^3$ pentru orice $i$ de la $2$ la $N$

Subtask 4 (20 de puncte)

$0 ≤ c_i ≤ 10^3$ pentru orice $i$ de la $2$ la $N$

Subtask 5 (5 puncte)

Toate valorile muchiilor sunt egale ( $c_i = c_j$ pentru orice $2 ≤ i, j ≤ N$ ).

Subtask 6 (10 puncte)

$1 ≤ N ≤ 10^3$

Subtask 7 (15 puncte)

Fără restricții suplimentare

Exemple

stdin

5	
1 1 2 1	
30 16 38 14

stdout