다리 철거

산호 제도는 한때 관광지로 인기가 많았다. 정부는 자연을 보전하려고 섬 출입을 막고 사람이 세운 시설을 모두 걷어내기로 했다. 이 사업에서 가장 까다로운 부분은 섬을 잇는 다리를 전부 철거하는 일이다.

섬은 $n$개, 다리는 $n-1$개다. 다리는 어느 섬에서 출발하든 다리를 한 개 이상 건너 나머지 모든 섬에 갈 수 있도록 놓여 있다. 철거반은 아무 섬에서나 시작할 수 있고, 다음 두 가지 작업을 원하는 순서로 되풀이한다.

• 지금 있는 섬에 연결된 다리를 건너 반대편 섬으로 이동한다.
• 지금 있는 섬에 연결된 다리 하나를 철거하고, 철거한 뒤에도 그 섬에 머무른다.

한 번 철거한 다리는 어느 방향으로도 건널 수 없다. 다리를 건너는 시간도, 철거하는 시간도 그 다리의 길이에 비례한다. 다리를 모두 철거하는 데 필요한 최소 시간을 구하라. 철거반이 출발한 섬과 작업을 끝낸 섬은 서로 달라도 된다.

입력은 데이터 집합 여러 개로 이루어지고, 데이터 집합은 최대 100개다. 각 데이터 집합의 형식은 다음과 같다.

n
p2 p3 ... pn
d2 d3 ... dn

첫 줄의 정수 $n$ ($3 \le n \le 800$)은 섬의 개수다. 섬에는 1번부터 $n$번까지 번호가 붙어 있다. 둘째 줄에는 섬 번호 $p_i$ ($1 \le p_i < i$)가 $n-1$개 주어진다. 이는 2부터 $n$까지의 각 $i$에 대해 섬 $i$와 섬 $p_i$가 다리로 이어져 있다는 뜻이다. 셋째 줄에는 정수 $d_i$ ($1 \le d_i \le 100000$)가 $n-1$개 주어진다. 섬 $i$와 섬 $p_i$를 잇는 다리의 길이가 $d_i$이고, 이 다리를 건너는 데 $d_i$, 철거하는 데도 $d_i$만큼의 시간이 걸린다. 이 입력 형식에서는 모든 섬이 서로 오갈 수 있음이 보장된다.

입력의 마지막 줄에는 0 하나만 주어진다.

각 데이터 집합마다 모든 다리를 철거하는 데 필요한 최소 시간을 한 줄에 출력한다. 각 줄에는 이 수 외에 어떤 문자도 넣지 않는다.