JOI 2026 - River Rafting
Xem PDFJOI có một cây gốc tại thành phố \(1\); có \(N\) thành phố và \(N-1\) con đường hai chiều. Đường thứ \(i\) nối \(P_i\) với \(i+1\) và dòng sông tương ứng chảy từ \(P_i\) đến \(i+1\). Mỗi thành phố có đúng một chiếc đèn. Ban đầu sức mạnh mọi đèn bằng \(0\) và không thành phố nào được chiếu sáng.
Có thể thực hiện từ \(0\) chuyến đi bè trở lên. Mỗi chuyến bắt đầu ở thành phố \(1\), đi theo một đường có hướng xuống cây và kết thúc tại một thành phố tùy chọn; sức mạnh đèn tại mỗi thành phố trên đường đi, kể cả hai đầu, tăng đúng \(1\). Có thể kết thúc chuyến đi ngay tại thành phố \(1\) mà không đi qua sông nào; đèn tại thành phố \(1\) vẫn tăng sức mạnh thêm \(1\). Nếu kết thúc tại thành phố \(t\), chuyến đi tốn \(C_t\).
Đèn sức mạnh \(l\) tại một thành phố chiếu sáng mọi thành phố có thể đến từ nó qua ít hơn \(l\) con đường hai chiều, không phụ thuộc chiều chảy của sông. Hãy tìm tổng chi phí nhỏ nhất để mọi thành phố được ít nhất một đèn chiếu sáng.
Dữ liệu vào
Dòng đầu chứa \(N\). Dòng thứ hai chứa \(P_1,\ldots,P_{N-1}\). Dòng thứ ba chứa \(C_1,\ldots,C_N\).
Dữ liệu ra
In tổng chi phí nhỏ nhất.
Ràng buộc
- \(2\le N\le700\).
- \(1\le P_i\le i\).
- \(1\le C_i\le10^9\).
- Mọi giá trị số trong dữ liệu vào đều là số nguyên.
Phân nhóm
- \(13\) điểm: \(N\le8\).
- \(25\) điểm: \(N\le100\).
- \(7\) điểm: \(P_i=1\) với mọi \(i\).
- \(11\) điểm: \(P_i=i\) với mọi \(i\).
- \(16\) điểm: mỗi thành phố là cha của nhiều nhất hai thành phố khác.
- \(28\) điểm: không có ràng buộc thêm.
Ví dụ
Ví dụ 1
Input
5
1 2 2 4
10 4 8 9 5Output
9Giải thích
Chuyến thứ nhất đi qua sông \(1\) và kết thúc ở thành phố \(2\), tăng sức mạnh đèn tại các thành phố \(1,2\) thêm \(1\), với chi phí \(4\). Chuyến thứ hai đi qua các sông \(1,3,4\) và kết thúc ở thành phố \(5\), tăng sức mạnh đèn tại các thành phố \(1,2,4,5\) thêm \(1\), với chi phí \(5\).
Sau đó, sức mạnh đèn tại các thành phố \(1,2\) bằng \(2\), tại thành phố \(3\) bằng \(0\), tại các thành phố \(4,5\) bằng \(1\). Đèn sức mạnh \(2\) ở thành phố \(2\) chiếu sáng các thành phố \(1,2,3,4\); đèn sức mạnh \(1\) ở thành phố \(5\) chiếu sáng thành phố \(5\). Tất cả thành phố đều được chiếu sáng với tổng chi phí \(4+5=9\). Không thể đạt yêu cầu với chi phí nhỏ hơn \(9\), nên in \(9\).
Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(5\), \(6\).
Ví dụ 2
Input
9
1 1 1 2 5 5 5 3
100 70 80 90 60 30 40 50 30Output
90Giải thích
Thực hiện hai chuyến đi qua các sông \(1,4,5\) và kết thúc ở thành phố \(6\), cùng một chuyến đi qua các sông \(2,8\) và kết thúc ở thành phố \(9\). Sau đó, sức mạnh đèn ở thành phố \(1\) bằng \(3\); ở các thành phố \(2,5,6\) bằng \(2\); ở các thành phố \(3,9\) bằng \(1\); ở các thành phố \(4,7,8\) bằng \(0\). Tất cả thành phố đều được chiếu sáng. Tổng chi phí là \(30\times2+30=90\). Không thể đạt yêu cầu với chi phí nhỏ hơn \(90\), nên in \(90\).
Ví dụ này thỏa mãn các nhóm \(2\), \(6\).
Nguồn
JOI 2025/2026 Semifinal Stage, bài River Rafting. Tài liệu gốc của Japanese Committee for IOI được phát hành theo CC BY-SA 4.0.
Kỳ thi:
- JOI 2026 - Bán kết (1 Tháng 2., 2026)
Bình luận