<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>


def kth_ancs(dp1,dp2,u, v,k):
    ans = 0
    for c in range(v-1,-1,-1):
        if k & (1 << c):
            a1, a2 = dp1[u][c],dp2[u][c]
            u = a1
            ans+=a2
    return ans

class Solution:
    def getMaxFunctionValue(self, arr: List[int], k: int) -> int:
        v = k
        v = v.bit_length()
        n = len(arr)
        # dp = [[[-1,-1] for c in range(v)] for i in range(n)]
        dp1 = [[-1 for c in range(v)] for i in range(n)]
        dp2 = [[-1 for c in range(v)] for i in range(n)]
        for i,j in enumerate(arr):
            dp1[i][0] = j
            dp2[i][0] = j

        for j in range(1,v):
            for i in range(n):
                c , d =  dp1[i][j-1], dp2[i][j-1]
                if c != -1:
                    a1 , d1 = dp1[c][j-1], dp2[c][j-1]
                    a2 = d + d1
                    dp1[i][j],dp2[i][j] = a1,a2
        ans = float('-inf')
        for i in range(n):
            if i==arr[i]:
                c = i * (k)
            else:
                c = kth_ancs(dp1,dp2,i, v, k)
            ans = max(ans, i+ c)
        return ans
        
# class Solution:
#     def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
#         n = len(receiver)
#         up = [[0 for _ in range(40)] for _ in range(n)]
#         dp = [[0 for _ in range(40)] for _ in range(n)]
#         for i in range(n):
#             j = receiver[i]
#             up[i][0] = j
#             dp[i][0] = j
#         for j in range(1, 40):
#             for i in range(n):
#                 j1 = up[up[i][j - 1]][j - 1]
#                 j2 = up[i][j - 1]
#                 up[i][j] = j1
#                 dp[i][j] = dp[i][j - 1] + dp[j2][j - 1]
#         ans = 0
#         for i in range(n):
#             tot = i
#             u = i
#             for j in range(40):
#                 if k & (1 << j) != 0:
#                     tot += dp[u][j]
#                     u = up[u][j]
#             ans = max(ans, tot)
#         return ans
7128