AT_joi2026_semifinal_d 川下り(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$。 每个城市都放有一个灯，每盏灯都有一个“强度”。如果城市 $t$（$1 \leq t \leq N$）的灯的强度为 $l$，则从该城市出发经过少于 $l$ 条道路可以到达的城市，都会被这盏灯照亮。初始时，所有灯的强度均为 $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. ($13$ 分)：$N \leq 8$。 2. ($25$ 分)：$N \leq 100$。 3. ($7$ 分)：$P_i = 1$（$1 \leq i \leq N-1$）。 4. ($11$ 分)：$P_i = i$（$1 \leq i \leq N-1$）。 5. ($16$ 分)：对于所有 $i$（$1 \leq i \leq N$），有 $P_j = i$ 的 $j$（$1 \leq j \leq N-1$）不超过 $2$ 个。 6. ($28$ 分)：无其他限制。 --- ### 样例解释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 \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$）。 - 输入的所有值均为整数。 由 ChatGPT 5 翻译