题目描述

题目译自 Open Olympiad in Informatics 2018 Day2 T3 「ООШП / OMOI」。

开放式轮胎修理工完美主义者协会（OMOI）是一个组织，由 N 市 $n$ 名轮胎修理工组成。协会内的所有轮胎修理工按加入顺序编号为从 $1$ 到 $n$ 的连续整数，并组成一个树状层级结构，其中编号为 $1$ 的修理工是协会的领导者，而其他修理工 $i$ 都有一个直接上级 $p_i$，其编号必然小于 $i$。我们称修理工 $v$ 是修理工 $u$ 的上级，如果 $v$ 出现在从 $u$ 到 $1$ 的直接上级链上，即序列 $p_u, p_{p_u}$ 等等。在这种情况下，修理工 $u$ 被称为修理工 $v$ 的下属。

由于 OMOI 的所有成员都是完美主义者，他们在工作中经常发生争执。我们假设争执只会发生在两个修理工之间，且这两个人中没有一个是另一个的下属。为了解决争执，他们会去找他们的最近共同上级，即编号最大的、同时是两个争执者上级的修理工。除了第一个修理工外，每个修理工都有一个完美主义等级，用整数 $c_i$ 表示。争执的激烈程度定义为参与争执的两个修理工的完美主义等级之和。最后，一个工作日的冲突度定义为该日发生的所有争执的激烈程度之和。

在工作日结束时，修理工 $v$ 认为自己是高效领导者，如果在这一天他至少帮助每个下属解决了一次争执。形式上，这意味着对于每个作为 $v$ 下属的修理工 $u$，存在一个修理工 $w$，使得 $u$ 和 $w$ 在当天发生了争执，而 $v$ 是 $u$ 和 $w$ 的最近共同上级。特别地，任何没有下属的修理工自动认为自己是高效领导者。

你是 OMOI 的程序员，认识组织内的所有修理工。今天下班时，公司内的每个修理工私下告诉你，他们在今天的工作日结束后认为自己是高效领导者。你知道 OMOI 修理工的层级结构，但不知道当天具体发生了哪些争执。现在，你想知道，在每个修理工确实是高效领导者的前提下，今天工作日的冲突度可能的最小值是多少。

输入格式

第一行包含一个整数 $n$ $(3 \leq n \leq 200000)$，表示 OMOI 中修理工的数量。

第二行包含 $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$ 的完美主义等级。

保证在给定的层级结构下，可能存在一种情况，使得工作日结束时每个修理工都认为自己是高效领导者。

输出格式

输出一个整数，表示在当天工作日冲突度的最小可能值。

5
1 2 2 1
1 1 1 1

8

在第一个样例中，为了达到指定的工作日冲突度，需要在当天发生以下争执：修理工对 $(2, 5)$、$(3, 4)$、$(3, 5)$ 和 $(4, 5)$。

• 修理工 $3$、$4$ 和 $5$ 自动认为自己是高效领导者，因为他们没有下属。
• 修理工 $2$ 认为自己是高效领导者，因为他帮助修理工 $3$ 解决了与修理工 $4$ 的争执，也帮助修理工 $4$ 解决了与修理工 $3$ 的争执。
• 修理工 $1$ 认为自己是高效领导者，因为他帮助修理工 $2$、$3$ 和 $4$ 解决了他们与修理工 $5$ 的冲突，同时帮助修理工 $5$ 解决了三个冲突。

每次争执的激烈程度为 $2 = 1 + 1$，因此当天的工作日冲突度为 $8$。

6
1 1 1 4 4
1 2 3 4 5

25

在第二个样例中（符合第二和第四组测试的限制，但不符合第一和第三组），最优解可以通过以下争执对获得：$(2, 5)$、$(3, 6)$、$(4, 5)$ 和 $(5, 6)$。在这种情况下，工作日冲突度为 $(1 + 3) + (1 + 4) + (2 + 5) + (4 + 5) = 25$。这种争执对组合并不是获得最小冲突度的唯一方式。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。