川下り(River Rafting)

JOI 国にはN 個の街があり,街には1 からN までの番号が付けられている.これらの街の間にはN −1
本の道があり,1 からN −1 までの番号が付けられている.道i (1 ≦i ≦N −1) は街Pi (Pi ≦i) と街i + 1
とを相互に結んでいる.街1 からどの街へも何本かの道を通って移動できることが保証されている.ま
た,JOI 国には道に並行する川がN −1 本あり,川には1 からN −1 までの番号が付けられている.川i
(1 ≦i ≦N −1) は道i と並行しており,街Pi から街i + 1 の向きに流れている.
N 個の街にはそれぞれ1 つずつランプが置いてある.各ランプには強さが定められている.街t (1 ≦t ≦
N) にあるランプの強さがl であるとき,その街からl 本未満の道を通って到達できる街はこのランプによっ
て照らされている.最初の時点では,ランプの強さはすべて0 であり,どの街も照らされていない.
あなたは川下りを0 回以上の好きな回数行うことが出来る.川下りは街1 にいる状態から始めて,まず街
1 にあるランプの強さを1 増やす.そして,以下の操作を順に繰り返す.
1. 川下りを終了するか決める.ただし今いる街から流れる川が存在しないときは必ず終了する.
2. 川下りを続ける場合,今いる街から流れる川を1 つ選び,その川の流れに沿って移動する.移動した
先の街のランプの強さを1 増やす.
川下りを街t で終了した場合,この川下りにかかるコストはCt である.あなたは,川下りを0 回以上の
好きな回数行うことで,すべての街がいずれかのランプによって照らされるようにしたい.その上で,川下
りにかかるコストの合計を最小化する必要がある.
道とコストの情報が与えられたとき,すべての街がいずれかのランプによって照らされるようにするため
の川下りにかかるコストの合計の最小値を求めるプログラムを作成せよ.

The 25^th Japanese Olympiad in Informatics (JOI 2025/2026)
Semifinal Stage
February 1, 2026 (Shimbashi, Tokyo)

• 2 ≦N ≦700.
• 1 ≦Pi ≦i (1 ≦i ≦N −1).
• 1 ≦Ct ≦109 (1 ≦t ≦N).
• 入力される値はすべて整数である.

1. (13 点) N ≦8.
2. (25 点) N ≦100.
3. (7 点) Pi = 1 (1 ≦i ≦N −1).
4. (11 点) Pi = i (1 ≦i ≦N −1).
5. (16 点) すべてのi (1 ≦i ≦N) に対して,Pj = i となるj (1 ≦j ≦N −1) は2 個以下.
6. (28 点) 追加の制約はない.

The 25^th Japanese Olympiad in Informatics (JOI 2025/2026)
Semifinal Stage
February 1, 2026 (Shimbashi, Tokyo)

入力は以下の形式で標準入力から与えられる.
N
P1 P2 · · · PN−1
C1 C2 · · · CN

標準出力に,すべての街がいずれかのランプによって照らされるようにするための川下りにかかるコスト
の合計の最小値を1 行で出力せよ.

생성자가 기록되지 않았습니다.

출처 JOI 2026 Semifinal