OMOI

Organization of Meticulous Oil Inspectors(OMOI)는 N시의 석유 검사관 $n$명으로 이루어진 협회이다. 검사관은 가입한 순서대로 $1$부터 $n$까지 번호가 붙는다. 검사관 $1$이 OMOI의 대표이고, 나머지 검사관 $i$에게는 자기보다 번호가 작은 직속 상사 $p_i$가 있다. 검사관 $v$가 $p_u$, $p_{p_u}$, 그 위 상사로 이어지는 사슬에 있으면 $v$는 $u$의 상사이고, $u$는 $v$의 부하이다.

두 검사관은 둘 중 누구도 상대의 상사가 아닐 때에만 논쟁할 수 있다. 논쟁한 두 검사관은 해결을 위해 가장 가까운 공통 상사, 즉 공통 상사 중 번호가 가장 큰 검사관에게 조언을 구한다. 대표를 제외한 검사관 $i$에게는 완벽주의 수준 $c_i$가 있다. 논쟁의 강도는 논쟁에 참여한 두 검사관의 완벽주의 수준의 합이다. 하루의 긴장도는 그날 벌어진 모든 논쟁의 강도를 합한 값이다.

하루가 끝날 때 검사관 $v$는 자신의 부하 $u$마다 $u$와 논쟁한 검사관 $w$가 있고 $v$가 둘의 가장 가까운 공통 상사인 경우, 스스로를 효과적인 관리자라고 생각한다. 부하가 없는 검사관은 자동으로 효과적인 관리자이다.

모든 검사관이 그날 자신이 효과적인 관리자였다고 보고했다. 이때 가능한 하루 긴장도의 최솟값을 구하라.

첫째 줄에 검사관 수 $n$ ($3 \leq n \leq 200\,000$)이 주어진다. 둘째 줄에는 $n-1$개의 정수 $p_2, p_3, \ldots, p_n$ ($1 \leq p_i < i$)이 주어지며, $p_i$는 검사관 $i$의 직속 상사 번호이다. 셋째 줄에는 $n-1$개의 정수 $c_2, c_3, \ldots, c_n$ ($1 \leq c_i \leq 10^6$)이 주어지며, $c_i$는 검사관 $i$의 완벽주의 수준이다.

주어진 계층에서 모든 검사관이 하루가 끝날 때 효과적인 관리자가 되는 것이 가능함이 보장된다.

가능한 하루 긴장도의 최솟값을 출력한다.

첫 번째 테스트 케이스를 보자. 긴장도가 최소가 되는 것은 $(2, 5)$, $(3, 4)$, $(3, 5)$, $(4, 5)$ 쌍이 논쟁할 때이다.

• 검사관 $3$, $4$, $5$는 부하가 없으므로 자동으로 효과적인 관리자이다.
• 검사관 $2$는 $3$과 $4$의 논쟁, 그리고 $4$와 $3$의 논쟁에서 가장 가까운 공통 상사였으므로 효과적인 관리자이다.
• 검사관 $1$은 $5$와 $2$, $3$, $4$의 논쟁에서 가장 가까운 공통 상사였고, $5$와 관련된 서로 다른 논쟁을 세 개 처리했으므로 효과적인 관리자이다.

각 논쟁의 강도는 $2 = 1 + 1$이므로, 이날의 긴장도는 $8$이다.