<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:
    # binary lifting
    # once we have dp table we can decompose k into powers of 2
    # and add appropriate dp vals
    def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
        N = len(receiver)
        P = 34
        # nxt[p][x] = receiver^(2^p)[x]
        # dp[p][x] = receiver[x] + receiver^2[x] + receiver^3[x] + ... + receiver^(2^p)[x] 
        nxt = [receiver[:] for _ in range(P)]
        dp = [list(range(N)) for _ in range(P)]
        for p in range(1, P):
            for x in range(N):
                nxt[p][x] = nxt[p-1][ nxt[p-1][x] ]
                dp[p][x] = dp[p-1][x] + dp[p-1][ nxt[p-1][x] ]
        
        res = 0
        for x in range(N):
            s = 0
            for p in range(P):
                if (k + 1) >> p & 1:
                    s += dp[p][x]
                    x = nxt[p][x]
            res = max(res, s)
        return res

    def getMaxFunctionValue(self, G: List[int], K: int) -> int:
        N = len(G)
        K += 1

        res = [-1] * N
        R = [[] for _ in range(N)]
        for u in range(N):
            R[G[u]].append(u)
        
        def dfs(u, i):
            for v in R[u]:
                if res[v] != -1: continue
                
                prv = path[-K] if len(path) >= K else cycle[i]
                res[v] = res[path[-1]] - prv + v
                
                path.append(v)
                dfs(v, (i - 1) % C)
                path.pop()

        for u in range(N):
            if res[u] != -1: continue
            # find cycle
            slo = G[u]
            fas = G[G[u]]
            while slo != fas:
                slo = G[slo]
                fas = G[G[fas]]
            
            # build cycle list
            cycle = []
            while True:
                cycle.append(slo)
                slo = G[slo]
                if slo == fas: break
            
            # init res[cycle[0]]
            C = len(cycle)
            S = sum(cycle)
            res[slo] = S * (K // C)
            for _ in range(K % C):
                res[slo] += fas
                fas = G[fas]
            
            # init res for rest of cycle
            for _ in range(C - 1):
                res[G[slo]] = res[slo] - slo + fas
                slo = G[slo]
                fas = G[fas]
            
            # run reverse dfs from each node in cycle
            for offset, start in enumerate(cycle):
                path = [start]
                dfs(start, (K % C - 1 + offset) % C)
        
        return max(res)
        # res array
        # reverse graph
        # 1. use floyds to get cycle meeting point
        # 2. loop thru cycle, build cycle list, get cycle sum
        # 3. init res[cycle_start] = S * K//C, then loop thru K%C times while res[cycle_tart] +=
        # (now we have slo ptr at start, fas ptr at end. ie. [slo, fas) is the range)
        # 4. loop thru entire cycle res[u] = res[u-1] - slo + fas, update slo and fas
        # (now everything in cycle should be set)

        # 5. loop thru entire cycle, reverse dfs at every node in cycle
        
        # dfs:
        # - track dis from cycle
        # - track path
        # if d > k:
        #     rolling sum from stack fram
        #     res[cur] = res[prv] + cur - path[-k]
        # else:
        #     res[cur] = res[prv] + cur - cycle

        # S (floor(K/C))
        # remainder = K % C
        # rolling sum to calc answer for nodes in cyc
        # cycle array
        # track depth of dfs and stack frame
        # if d > k:
        #     rolling sum from stack frame
        # else:
        #     + prev - cycle
582