G. Chakra rezonansi

Konoha ninjalari orasidagi ustoz–shogird munosabati \(n\) tugunli daraxt hosil qiladi: tugun \(1-\)Hokage (ildiz), qolgan har bir ninja \(i\) (\(2 ≤ i ≤ n\)) uchun uning bevosita ustozi \(p_i \) beriladi. Har bir ninja \(i\) ning jangovar kuchi \(w_i \) bilan berilgan.

Besh Kage anjumanini himoya qilish uchun maxsus otryad tuzilmoqda. Ammo Konoha tadqiqotchilari xavfli hodisani aniqladi: agar otryadga daraxt bo'yicha masofasi \(2\) yoki undan kam bo'lgan ikkita ninja kiritilsa, ularning chakralari rezonansga kirib, jang paytida ikkalasi ham ishlatib bo'lmay qoladi. Shu sababli otryadga kiritilgan istalgan ikki ninja orasidagi daraxt bo'yicha masofa (ular orasidagi eng qisqa yo'ldagi qirralar soni) kamida \(3\) bo'lishi shart.

Hokage otryadga kirgan ninjalarning jangovar kuchlari yig'indisini maksimal qilmoqchi. Ushbu maksimal yig'indini toping.

Kiruvchi ma'lumotlar

Birinchi qatorda bitta butun son \(n\) beriladi.

Ikkinchi qatorda \(n-1\) ta butun son \(p_2, p_3, …, p_n\) beriladi — \(p_i \) ninja \(i\) ning bevosita ustozi (\(1 ≤ p_i < i\)). Bu massiv har doim to'g'ri daraxt hosil qilishini kafolatlaydi.

Uchinchi qatorda \(n\) ta butun son \(w_1, w_2, …, w_n\) — ninjalarning jangovar kuchlari.

\(2 ≤ n ≤ 2 \times 10^5 \)
\(1 ≤ p_i < i\)
\(1 ≤ w_i ≤ 10^9\)

Chiquvchi ma'lumotlar

Bitta butun son - otryadga kiritilishi mumkin bo'lgan ninjalarning jangovar kuchi yig'indisining maksimal qiymatini chop eting.

Misollar

1

7
1 1 2 2 3 3
5 3 9 1 4 2 7

13

2

6
1 2 3 4 5
10 10 10 10 10 10

20

3

5
1 1 1 1
100 7 7 7 7

100