该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile5604.zip](file://AdditionalFile5604.zip?type=additional_file)

#5604. 「JOI 2026 Semifinal」漂流

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Semifinal T4 「川下り / River Rafting」

JOI 国有 $N$ 个城市，城市编号为 $1$ 到 $N$。这些城市之间有 $N-1$ 条道路，编号为 $1$ 到 $N-1$。道路 $i$ $(1 \leq i \leq N-1)$ 连接着城市 $P_{i}$ $(P_{i} \leq i)$ 和城市 $i+1$。保证从城市 $1$ 出发可以通过若干条道路到达任意一个城市。此外，JOI 国还有 $N-1$ 条与道路平行的河流，编号为 $1$ 到 $N-1$。河流 $i$ $(1 \leq i \leq N-1)$ 与道路 $i$ 平行，流向是从城市 $P_{i}$ 到城市 $i+1$。

$N$ 个城市中每个城市都放置了一盏路灯。每盏路灯都有设定的强度。当位于城市 $t$ $(1 \leq t \leq N)$ 的路灯强度为 $l$ 时，从该城市出发通过少于 $l$ 条道路能够到达的城市都会被这盏路灯照亮。在初始时刻，所有路灯的强度都是 $0$，没有任何城市被照亮。

你可以进行任意次数（$0$ 次或更多）的漂流。一次漂流从身处城市 $1$ 开始，首先将城市 $1$ 的路灯强度增加 $1$。然后，按顺序重复以下操作：

1. 决定是否结束漂流。但是，如果当前所在的城市没有流出的河流，则必须结束。
2. 如果继续漂流，选择一条从当前城市流出的河流，顺着河流移动。将移动到的目标城市的路灯强度增加 $1$。

如果在城市 $t$ 结束漂流，则该次漂流的费用为 $C_{t}$。你想通过进行任意次数的漂流，使得所有城市都被至少一盏路灯照亮。在此基础上，需要使漂流的总费用最小化。

给定道路和费用的信息，请编写一个程序，求出为了使所有城市都被照亮，漂流所需的最小总费用。

输入格式

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

第二行包含用空格分隔的 $N-1$ 个整数 $P_1, P_2, \ldots P_{N-1}$。

第三行包含用空格分隔的 $N$ 个整数 $C_1, C_2, \ldots C_N$。

输出格式

输出一行，表示为了使所有城市都被照亮所需的漂流最小总费用。

样例 1

输入

5
1 2 2 4
10 4 8 9 5

输出

9

第 $1$ 次漂流选择河流 $1$，在城市 $2$ 结束漂流。此时城市 $1, 2$ 的路灯强度增加 $1$，费用为 $4$。

第 $2$ 次漂流选择河流 $1, 3, 4$，在城市 $5$ 结束漂流。此时城市 $1, 2, 4, 5$ 的路灯强度增加 $1$，费用为 $5$。

操作后，城市 $1, 2$ 的路灯强度为 $2$，城市 $3$ 的路灯强度为 $0$，城市 $4, 5$ 的路灯强度为 $1$。

城市 $1, 2, 3, 4$ 被位于城市 $2$ 强度为 $2$ 的路灯照亮（距离小于 2 的城市），城市 $5$ 被位于城市 $5$ 强度为 $1$ 的路灯照亮。

因此，通过这些操作，所有城市都被照亮。此时总费用为 $4+5=9$。

无法以小于 $9$ 的费用满足条件，因此输出 $9$。

此样例满足子任务 $1, 2, 5, 6$ 的限制。

样例 2

输入

9
1 1 1 2 5 5 5 3
100 70 80 90 60 30 40 50 30

输出

90

进行 $2$ 次经过河流 $1, 4, 5$ 并结束于城市 $6$ 的漂流，以及 $1$ 次经过河流 $2, 8$ 并结束于城市 $9$ 的漂流。

操作后，城市 $1$ 的路灯强度为 $3$，城市 $2, 5, 6$ 的路灯强度为 $2$，城市 $3, 9$ 的路灯强度为 $1$，城市 $4, 7, 8$ 的路灯强度为 $0$。

通过这些操作，所有城市都被照亮。此时总费用为 $30 \times 2 + 30 = 90$。

无法以小于 $90$ 的费用满足条件，因此输出 $90$。

此样例满足子任务 $2, 6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 700$
• $1 \leq P_{i} \leq i$ $(1 \leq i \leq N-1)$
• $1 \leq C_{t} \leq 10^{9}$ $(1 \leq t \leq N)$
• 输入的所有值均为整数。

详细子任务附加限制及分值如下表所示。