<p>You are given an integer array <code>receiver</code> of length <code>n</code> and an integer <code>k</code>. <code>n</code> players are playing a ball-passing game.</p>

<p>You choose the starting player, <code>i</code>. The game proceeds as follows: player <code>i</code> passes the ball to player <code>receiver[i]</code>, who then passes it to <code>receiver[receiver[i]]</code>, and so on, for <code>k</code> passes in total. The game&#39;s score is the sum of the indices of the players who touched the ball, including repetitions, i.e. <code>i + receiver[i] + receiver[receiver[i]] + ... + receiver<sup>(k)</sup>[i]</code>.</p>

<p>Return&nbsp;the <strong>maximum</strong>&nbsp;possible score.</p>

<p><strong>Notes:</strong></p>

<ul>
	<li><code>receiver</code> may contain duplicates.</li>
	<li><code>receiver[i]</code> may be equal to <code>i</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">receiver = [2,0,1], k = 4</span></p>

<p><strong>Output:</strong> <span class="example-io">6</span></p>

<p><strong>Explanation:</strong></p>

<p>Starting with player <code>i = 2</code> the initial score is 2:</p>

<table>
	<tbody>
		<tr>
			<th>Pass</th>
			<th>Sender Index</th>
			<th>Receiver Index</th>
			<th>Score</th>
		</tr>
		<tr>
			<td>1</td>
			<td>2</td>
			<td>1</td>
			<td>3</td>
		</tr>
		<tr>
			<td>2</td>
			<td>1</td>
			<td>0</td>
			<td>3</td>
		</tr>
		<tr>
			<td>3</td>
			<td>0</td>
			<td>2</td>
			<td>5</td>
		</tr>
		<tr>
			<td>4</td>
			<td>2</td>
			<td>1</td>
			<td>6</td>
		</tr>
	</tbody>
</table>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">receiver = [1,1,1,2,3], k = 3</span></p>

<p><strong>Output:</strong> <span class="example-io">10</span></p>

<p><strong>Explanation:</strong></p>

<p>Starting with player <code>i = 4</code> the initial score is 4:</p>

<table>
	<tbody>
		<tr>
			<th>Pass</th>
			<th>Sender Index</th>
			<th>Receiver Index</th>
			<th>Score</th>
		</tr>
		<tr>
			<td>1</td>
			<td>4</td>
			<td>3</td>
			<td>7</td>
		</tr>
		<tr>
			<td>2</td>
			<td>3</td>
			<td>2</td>
			<td>9</td>
		</tr>
		<tr>
			<td>3</td>
			<td>2</td>
			<td>1</td>
			<td>10</td>
		</tr>
	</tbody>
</table>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= receiver.length == n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= receiver[i] &lt;= n - 1</code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>10</sup></code></li>
</ul>

class Solution:
    def getMaxFunctionValue(self, rcv: List[int], k: int) -> int:
        n = len(rcv)
        path_val = [0] * n
        circle_arr = [None] * n
        indeg = [0] * n
        for e in rcv:
            indeg[e] += 1
        
        def compute_circle(psum, i, rem):
            # sum(circle[i+1, ... i+rem]), circle is represented as partial-sum
            if i + rem < len(psum):
                return psum[i+rem] - psum[i]
            return psum[-1] - psum[i] + psum[i+rem-len(psum)]
        
        def build_path(s):
            visited = [0] * n
            visited[s] = 1
            path = [s]
            e = rcv[s]
            # find circle
            while visited[e] == 0 and circle_arr[e] == None:
                visited[e] = 1
                path.append(e)
                e = rcv[e]
            c_start = e
            if circle_arr[e] == None:
                # compute solutions for each node on the circle
                c_start_index = [i for i, node in enumerate(path) if node == c_start][0]
                c_val = sum(path[c_start_index:])
                c_len = len(path) - c_start_index
                circle_psum = path[c_start_index:]
                for i in range(1, len(circle_psum)):
                    circle_psum[i] = circle_psum[i-1] + circle_psum[i]
                rem_k = k % c_len
                for i in range(c_start_index, len(path)):
                    circle_arr[path[i]] = (i-c_start_index, circle_psum)
                    path_val[path[i]] = path[i] + k // c_len * c_val + compute_circle(circle_psum, i-c_start_index, rem_k)
            else:
                c_start_index = len(path)
                path.append(c_start)
            
            # compute solution for each node on the prefix-path
            path_psum = path[:]
            for i in range(1, len(path_psum)):
                path_psum[i] += path_psum[i-1]
            for i in range(c_start_index):
                pref_len = c_start_index - i
                if pref_len >= k:
                    path_val[path[i]] = path_psum[i+k] - (path_psum[i-1] if i > 0 else 0) #sum(path[i:i+k+1])
                else:
                    path_val[path[i]] = path_psum[c_start_index] - (path_psum[i-1] if i > 0 else 0) #sum(path[i:c_start_index+1])
                    rem_k = k - pref_len
                    cst, circle = circle_arr[c_start]
                    path_val[path[i]] += rem_k // len(circle) * circle[-1]
                    rem_k = rem_k % len(circle)
                    path_val[path[i]] += compute_circle(circle, cst, rem_k)
                
        # a prefix connected to a circle: a->b->c->(d->e->f->d)
        for s in range(n):
            if indeg[s] == 0:
                build_path(s)
        
        # handle pure circles with no 'prefix'
        for s in range(n):
            if path_val[s] == 0:
                build_path(s)
        return max(path_val)
6511