题目描述

Anton 是一名保安，负责看守编号为 $1$ 到 $n$ 的 $n$ 个物体。

有 $n-1$ 条道路，第 $i$ 条道路连接物体 $u_i$ 和 $v_i$，长度为 $w_i$。保证可以从物体 $1$ 到达任意其他物体。

一开始，Anton 位于物体 $1$。

定义每个物体的优先级为：从该物体到物体 $1$ 需要经过的最少道路条数。

例如，物体 $1$ 的优先级为 $0$；所有与物体 $1$ 直接相连的物体优先级为 $1$；依此类推。

Anton 需要访问所有物体。他必须先访问所有优先级为 $1$ 的物体，然后访问所有优先级为 $2$ 的物体，再访问所有优先级为 $3$ 的物体，依此类推。

如果有多个物体具有相同优先级，Anton 可以自行决定访问它们的顺序。注意，只有在访问完所有优先级为 $k-1$ 的物体之后，Anton 才能访问任何优先级为 $k$ 的物体。

请你求出 Anton 至少需要行走的总距离。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n-1$ 个整数 $p_i$，表示物体 $i+1$ 与物体 $p_i$ 之间有一条道路。

第三行包含 $n-1$ 个整数 $w_i$，表示物体 $i+1$ 与物体 $p_i$ 之间道路的长度。

保证可以从物体 $1$ 到达所有其他物体。

输出格式

输出一个整数，表示 Anton 需要行走的最小总距离。

数据范围

对于所有测试数据：

对于所有 $i=1,2,\ldots,n-1$：

输入 #1

7
3 1 1 1 5 6
14 10 6 5 7 3

输出 #1

85

子任务

1. $4$ 分：$1 \le n \le 10$；
2. $5$ 分：$1 \le n \le 22$；
3. $13$ 分：同一优先级的物体数量不超过 $6$；
4. $10$ 分：同一优先级的物体数量不超过 $10$；
5. $15$ 分：$w_i=1$；
6. $15$ 分：$1 \le n \le 10^5$；
7. $38$ 分：无额外限制。