006 - 橋の撤去

ICPC諸島は，かつて観光地として親しまれていたが， このたび，自然保護のため，全ての人工施設を撤廃して人の立ち入りを禁止することが決定された． このプロジェクトでいちばん難しいのは島々を結ぶ橋をすべて撤去することである．

ICPC諸島には島の数 n に対して n-1 個の橋があり，どの島から島へも， 橋を何回か渡れば到達することができるようになっている． 橋の撤去工事の作業チームは，好きな島からスタートして，繰り返し以下のいずれかの行動をとることができる．

• 今いる島に繋がっている橋を一つ渡って隣の島に移動する．
• 今いる島に繋がっている橋を一つ撤去する．撤去作業後は同じ島に留まる．

ただし当然ながら，一度撤去してしまった橋は二度と，どちらの方向にも渡ることができない． 橋を渡る場合も，橋を撤去する場合も，橋の長さに比例する時間がかかる． 全ての橋を撤去するのに必要な最短の時間を求めて欲しい． 作業チームのスタートする島と作業を終える島が異なっていても構わない．

入力は100個以下のデータセットからなる． 各データセットは以下の形式をしている．

n
p₂ p₃ ... p_n
d₂ d₃ ... d_n

n は島の数 (3 ≤ n ≤ 800) を表す．島には 1 から n までの識別番号が振られている． 2行目には n-1 個の島番号が並べられており (1 ≤ p_i < i)， 2 から n までの島 i について i と p_i が橋で直接繋がれていることを意味する． 3行目の n-1 個の正整数は対応する橋の長さを表す (1 ≤ d_i ≤ 100,000)． すなわち，i と p_i を結ぶ橋の長さは d_i である． この橋を渡るのには d_i 単位の時間がかかり，撤去にも同じだけの時間がかかる． なお，この入力形式では，全ての島と島の間が到達可能であるという条件は常に満たされている．

入力の終わりは，一つのゼロのみを含む行で示される．

各データセットについて，全部の橋を撤去するのに必要な最短の単位時間数を，1行に出力せよ． 各出力行はこの数値以外の文字を含んではならない．

4
1 2 3
10 20 30
10
1 2 2 1 5 5 1 8 8
10 1 1 20 1 1 30 1 1
3
1 1
1 1
0

80
136
2