P15454 [JOI 2026 SemiFinal] 顺流而下 / River Rafting

JOI 国有 $N$ 个城镇，城镇编号为 $1$ 到 $N$。这些城镇之间有 $N-1$ 条道路，编号为 $1$ 到 $N-1$。道路 $i$ ($1 \le i \le N-1$) 双向连接城镇 $P_i$ ($P_i \le i$) 和城镇 $i+1$。保证从城镇 $1$ 出发，可以通过若干条道路到达任意城镇。 此外，JOI 国有 $N-1$ 条与道路平行的河流，河流编号为 $1$ 到 $N-1$。河流 $i$ ($1 \le i \le N-1$) 与道路 $i$ 平行，从城镇 $P_i$ 流向城镇 $i+1$。 $N$ 个城镇中各放置了一盏灯。每盏灯都有一个强度。当城镇 $t$ ($1 \le t \le N$) 处的灯强度为 $l$ 时，从该城镇出发，经过少于 $l$ 条道路可以到达的城镇都会被这盏灯照亮。初始时，所有灯的强度均为 $0$，没有任何城镇被照亮。 你可以进行任意次（包括 $0$ 次）顺流而下。每次顺流而下从位于城镇 $1$ 的状态开始，首先将城镇 $1$ 处的灯强度增加 $1$。然后，依次重复以下操作： 1. 决定是否结束本次顺流而下。但如果当前所在城镇没有流出的河流，则必须结束。 2. 若继续顺流而下，则从当前城镇流出的河流中选择一条，沿着该河流移动。移动后，将到达的城镇处的灯强度增加 $1$。 若在城镇 $t$ 结束本次顺流而下，则此次顺流而下产生的成本为 $C_t$。你希望通过进行若干次顺流而下，使得每个城镇都至少被一盏灯照亮。在此基础上，需要最小化顺流而下产生的总成本。

输入从标准输入中以以下格式给出： $N$ $P_1\ P_2\ \cdots\ P_{N-1}$ $C_1\ C_2\ \cdots\ C_N$

向标准输出以一行输出使得每个城镇都至少被一盏灯照亮所需的顺流而下总成本的最小值。

#### 样例解释 1 第一次顺流而下选择河流 $1$，在城镇 $2$ 结束。此时，城镇 $1,2$ 的灯强度各增加 $1$，成本为 $4$。第二次顺流而下选择河流 $1,3,4$，在城镇 $5$ 结束。此时，城镇 $1,2,4,5$ 的灯强度各增加 $1$，成本为 $5$。 操作后，城镇 $1,2$ 的灯强度为 $2$，城镇 $3$ 的灯强度为 $0$，城镇 $4,5$ 的灯强度为 $1$。城镇 $1,2,3,4$ 被城镇 $2$ 处强度为 $2$ 的灯照亮，城镇 $5$ 被城镇 $5$ 处强度为 $1$ 的灯照亮。因此，通过这些操作，所有城镇都被某盏灯照亮。此时总成本为 $4 + 5 = 9$。无法以小于 $9$ 的成本满足条件，因此输出 $9$。 该输入样例满足子任务 $1,2,5,6$ 的数据范围。 #### 样例解释 2 进行两次沿河流 $1,4,5$ 到达城镇 $6$ 结束的顺流而下，以及一次沿河流 $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 \le N \le 700$ - $1 \le P_i \le i$ ($1 \le i \le N-1$) - $1 \le C_t \le 10^9$ ($1 \le t \le N$) - 输入的所有值均为整数。 ### 子任务 1. (13 分) $N \le 8$ 2. (25 分) $N \le 100$ 3. (7 分) $P_i = 1$ ($1 \le i \le N-1$) 4. (11 分) $P_i = i$ ($1 \le i \le N-1$) 5. (16 分) 对于每个 $i$ ($1 \le i \le N$)，满足 $P_j = i$ 的 $j$ ($1 \le j \le N-1$) 的个数不超过 $2$ 个 6. (28 分) 无额外限制 翻译由 DeepSeek 完成