P15454 [JOI 2026 SemiFinal] Going Downstream / River Rafting

In the country of JOI, there are $N$ towns, numbered from $1$ to $N$. Between these towns there are $N - 1$ roads, numbered from $1$ to $N - 1$. Road $i$ ($1 \le i \le N - 1$) bidirectionally connects town $P_i$ ($P_i \le i$) and town $i + 1$. It is guaranteed that starting from town $1$, you can reach any town by traveling along some roads. In addition, JOI has $N - 1$ rivers parallel to the roads, numbered from $1$ to $N - 1$. River $i$ ($1 \le i \le N - 1$) is parallel to road $i$, and flows from town $P_i$ to town $i + 1$. Each of the $N$ towns has a lamp. Each lamp has an intensity. If the lamp at town $t$ ($1 \le t \le N$) has intensity $l$, then all towns that can be reached from town $t$ by traveling along fewer than $l$ roads are illuminated by this lamp. Initially, all lamps have intensity $0$, and no town is illuminated. You may perform the operation “going downstream” any number of times (including $0$ times). Each time you go downstream, you start from being at town $1$, and first increase the lamp intensity at town $1$ by $1$. Then, you repeatedly perform the following steps in order: 1. Decide whether to end this downstream trip. However, if there is no outgoing river from the current town, you must end. 2. If you continue going downstream, choose one river among the rivers flowing out of the current town, and move along that river. After moving, increase the lamp intensity at the town you arrive at by $1$. If you end the downstream trip at town $t$, then the cost of this downstream trip is $C_t$. You want to perform some number of downstream trips so that every town is illuminated by at least one lamp. Under this condition, minimize the total cost of all downstream trips.

Input is given from standard input in the following format: $N$ $P_1\ P_2\ \cdots\ P_{N-1}$ $C_1\ C_2\ \cdots\ C_N$

Print, in one line, the minimum possible total cost of downstream trips required to make every town illuminated by at least one lamp.

#### Sample Explanation 1 In the first downstream trip, choose river $1$ and end at town $2$. Then, the lamp intensities of towns $1, 2$ each increase by $1$, and the cost is $4$. In the second downstream trip, choose rivers $1, 3, 4$ and end at town $5$. Then, the lamp intensities of towns $1, 2, 4, 5$ each increase by $1$, and the cost is $5$. After these operations, the lamp intensity of towns $1, 2$ is $2$, the lamp intensity of town $3$ is $0$, and the lamp intensity of towns $4, 5$ is $1$. Towns $1, 2, 3, 4$ are illuminated by the lamp at town $2$ with intensity $2$, and town $5$ is illuminated by the lamp at town $5$ with intensity $1$. Therefore, after these operations, all towns are illuminated by some lamp. The total cost is $4 + 5 = 9$. It is impossible to satisfy the condition with a cost smaller than $9$, so output $9$. This input sample satisfies the Constraints of subtasks $1, 2, 5, 6$. #### Sample Explanation 2 Perform two downstream trips that go along rivers $1, 4, 5$ and end at town $6$, and one downstream trip that goes along rivers $2, 8$ and ends at town $9$. After these operations, the lamp intensity of town $1$ is $3$; the lamp intensities of towns $2, 5, 6$ are $2$; the lamp intensities of towns $3, 9$ are $1$; and the lamp intensities of towns $4, 7, 8$ are $0$. Through these operations, all towns are illuminated by some lamp. The total cost is $30 \times 2 + 30 = 90$. It is impossible to satisfy the condition with a cost smaller than $90$, so output $90$. This input sample satisfies the Constraints of subtasks $2, 6$. ### Constraints - $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$) - All input values are integers. ### Subtasks 1. (13 points) $N \le 8$ 2. (25 points) $N \le 100$ 3. (7 points) $P_i = 1$ ($1 \le i \le N-1$) 4. (11 points) $P_i = i$ ($1 \le i \le N-1$) 5. (16 points) For each $i$ ($1 \le i \le N$), the number of $j$ ($1 \le j \le N-1$) such that $P_j = i$ is at most $2$ 6. (28 points) No additional constraints Translated by DeepSeek. Translated by ChatGPT 5