First, consider a graph whose vertices correspond to the squares and that has edges from \(i\) to \(P_i\). This graph consists of several cycles. Since the moves is performed only in the cycle that the piece’s square belongs, so it is sufficient to solve independently for each cycle and then take the maximum value.

The score is a sum of \(C_{P_i}\), but we can assume that it is a sum of \(C_i\) by shifting the whole path.

What is the shape of path that the piece passed? Starting from a square, it goes around the cycle for several (\(0\) or more) times, then stop at a square. The “remainder” of the cycle can be brute-forced, while it is optimal to use the cycle as much as possible if the sum of the cycle is positive, or otherwise not to use it at all.

By the foregoing procedures, the problem can be solved in a total of \(O(N^2)\) time.

Sample Code(C++)

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