まず、頂点集合がマスに対応して、\(i\) から \(P_i\) に有向辺を張ったグラフとして考えてみましょう。このグラフは、何個かのサイクルを集めた形になっています。移動は置かれたマスの属するサイクル上でのみ行われるので、各サイクルについて独立に解いた後、最大値を取れば良いです。

スコアは \(C_{P_i}\) の和の形になっていますが、移動した経路全体を \(1\) つずらすことで、\(C_i\) の和と思っても良いです。

コマの通った経路がどのような形をしているかをもう少し考えてみましょう。すると、あるマスから始めて、何周 (\(0\) でもよい)かサイクル全体を回った後、あるマスで終わるというような形をしています。このサイクルの「余り」の部分を全て試すことにすると、サイクルの和が正のときは使えるだけ使って、そうでないときは全く使わないのが最適です。

以上により時間計算量は \(\mathrm{O}(N^2)\) でこの問題を解くことができます。

実装例(C++)

bonus : \(N \leq 2 \times 10^5\)