2836-在传球游戏中最大化函数值

给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。

总共有 n 名玩家，玩家 编号 互不相同，且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏，receiver[i]
表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己，也就是说 receiver[i] 可能等于 i 。

你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家，球会被传 恰好 k 次。

如果选择编号为 x 的玩家作为开始玩家，定义函数 f(x) 表示从编号为 x 的玩家开始，k 次传球内所有接触过球玩家的编号之 和
，如果有玩家多次触球，则 累加多次 。换句话说， `f(x) = x + receiver[x] + receiver[receiver[x]]

• … + receiver(k)[x]` 。

你的任务时选择开始玩家 x ，目的是 ** 最大化** f(x) 。

请你返回函数的 最大值 。

注意：receiver 可能含有重复元素。

示例 1：

传递次数	传球者编号	接球者编号	x + 所有接球者编号
		2
1	2	1	3
2	1	0	3
3	0	2	5
4	2	1	6

**输入：** receiver = [2,0,1], k = 4
**输出：** 6
**解释：** 上表展示了从编号为 x = 2 开始的游戏过程。
从表中可知，f(2) 等于 6 。
6 是能得到最大的函数值。
所以输出为 6 。

示例 2：

传递次数	传球者编号	接球者编号	x + 所有接球者编号
		4
1	4	3	7
2	3	2	9
3	2	1	10

**输入：** receiver = [1,1,1,2,3], k = 3
**输出：** 10
**解释：** 上表展示了从编号为 x = 4 开始的游戏过程。
从表中可知，f(4) 等于 10 。
10 是能得到最大的函数值。
所以输出为 10 。

提示：

• 1 <= receiver.length == n <= 105
• 0 <= receiver[i] <= n - 1
• 1 <= k <= 1010

解法一：倍增算法

这也是一个典型的倍增算法应用题，LC应该之前很少考过倍增算法，所以这次好多人寄了。不过可以一步一步看下这个题的思路，后续遇到就不怕了。

令 f[i][j] = 从位置 i 开始，传球 2^j 次所能到达的位置；w[i][j] 为从位置 i 开始，传球 2^j 次所经过的路径的权值和（不包括终点）。

当 j=0 时，传 1 次球所能到到的位置为 receiver[i]、传 1 次球经过的权值和（不包括终点）为 i：

• f[i][0] = receiver[i]
• w[i][0] = i

当 j > 0 时，从 i 开始，传 2^j 次球，相当于从 i 开始，先传 2^{j-1 次球，到达 mid = f[i][j-1]；然后从 mid 开始，再传 2^{j-1 次球，到达终点。因此可以用下面的递推式子求 f[i][j] 和 w[i][j]：

• f[i][j]_{(j > 0)} = f[f[i][j-1]][j-1]
• w[i][j]_{(j > 0)} = w[i][j-1] + w[f[i][j-1]][j-1]

预处理完成后，我们对每个起点 i，可以快速求出从 i 开始跳 k 步的权值和：

• 首先对 k 按二进制拆位，分解成多个 2 的幂的和，即 k = 2^{p_1} + 2^{p_2} + … 2^{p_m。
• 然后对每一个二进制位求跳 2^i 步的权值和，累加可得出整个路径上的权值和（不包括终点）。
• 最后再加上终点的权值即可。

时间复杂度：O(n\log(k))。

空间复杂度：O(n\log(k))。

class Solution {
public:
    long long getMaxFunctionValue(vector<int>& a, long long k) {
        int n = a.size();
        int f[n][36];
        long long w[n][36];
        for(int i = 0; i < n; ++i) {
            f[i][0] = a[i];
            w[i][0] = i;
        }
        for(int j = 1; j < 36; ++j) {
            for(int i = 0; i < n; ++i) {
                f[i][j] = f[f[i][j-1]][j-1];
                w[i][j] = w[i][j-1] + w[f[i][j-1]][j-1];
            }
        }
        long long res = 0;
        for(int i = 0; i < n; ++i) {
            long long cur = 0;
            int pos = i;
            for(int j = 0; j < 36; ++j) {
                if((k >> j) & 1) {
                    cur += w[pos][j];
                    pos = f[pos][j];
                }
            }
            res = max(res, cur + pos);
        }
        return res;
    }
};

解法二：O(n) 基环树 + 分类讨论

首先根据题意建图：对于每个玩家 i，从 i 向 receiver[i] 连一条边。

根据性质（每个节点只连一条有向边），整个图可以分成一个或多个互不相连的 “基环树”。“基环树” 是指整个树中只有一个环作为 “核心”，其它节点都是环的 “分支”，并指向环内，如下图所示。

如果我们从下图中的绿色节点出发，走一定数量的节点，那么其路径将为：

• “环外” 部分，即下图中的第 1 段；
• 走几圈 “完整的环”，即下图中的第 2 段；
• 走完环内剩下的部分，即下图中的第 3 段。

因此整个问题的解法为：

• 首先找出图中所有的基环树。
• 然后从环上的每个节点进行 dfs，途中求出从每个节点出发，经过 k 个节点之后的路径权值和。具体求法参考上图，细节参考代码。
• 最后返回所有权值和的最大值。

class Solution {
public:
    long long getMaxFunctionValue(vector<int>& a, long long k) {
        int n = a.size();
        vector<int> nes[n], rnes[n];
        vector<int> deg(n, 0);
        for(int i = 0; i < n; ++i) {
            nes[i].push_back(a[i]);
            rnes[a[i]].push_back(i);
            deg[a[i]]++;
        }
        queue<int> q;
        for(int i = 0; i < n; ++i) {
            if(deg[i] == 0) {
                q.push(i);
            }
        }
        while(q.size()) {
            int cur = q.front(); q.pop();
            for(int ne : nes[cur]) {
                if(--deg[ne] == 0) {
                    q.push(ne);
                }
            }
        }
        
        vector<vector<long long>> pts;          /* pts[i] = 环内的点 */
        vector<int> len;                        /* len[i] = 环 i 的长度 */
        vector<int> cycle(n, -1), idx(n, -1);   /* cycle[i] = 点在哪个环上; idx[i] = 点在环的哪个位置 */
        for(int i = 0; i < n; ++i) {
            if(deg[i] && cycle[i] == -1) {
                pts.push_back({0});
                int cur = i;
                do {
                    pts.back().push_back(cur);
                    cycle[cur] = pts.size() - 1;
                    idx[cur] = pts.back().size() - 1;
                    cur = a[cur];
                } while(cur != i);
                len.push_back(pts.back().size() - 1);
            }
        }
        for(auto& v : pts) {
            for(int len = v.size(), i = 1; i < len; ++i)
                v.push_back(v[i]);
            for(int i = 1; i < v.size(); ++i)
                v[i] += v[i-1];
        }
        
        vector<long long> st({0});
        long long res = 0;
        function<void(int, int)> dfs = [&](int root, int node) {
            auto &v = pts[cycle[root]];
            long long out = min((long long)st.size() - 1, k+1), in = k+1 - out;
            res = max(res, 
                      st.back() - st[st.size() - 1 - out]                          /* 环外的部分 */
                      + (in / len[cycle[root]]) * v[len[cycle[root]]]              /* 环内完整的数量 */
                      + v[idx[root] + in % len[cycle[root]] - 1] - v[idx[root]-1]  /* 环内残缺的部分 */);
            for(int ne : rnes[node]) {
                if(deg[ne] == 0) {
                    st.push_back(st.back() + ne);
                    dfs(root, ne);
                    st.pop_back();
                }
            }
        };
        
        for(int i = 0; i < n; ++i) {
            if(deg[i]) {
                dfs(i, i);
            }
        }
        
        return res;
    }
};