【题目描述】
有 n 名玩家,编号为 0,1,…,n−1。给定一个长度为 n 的数组 receiver,其中 receiver[i] 表示玩家 i 会将球传给玩家 receiver[i](允许传给自己)。 现在你需要选择一名玩家作为起始持球者,然后球会被恰好传递 k 次。
定义函数 f(x) 为:从玩家 x 开始,经过 k 次传球,所有接触过球的玩家编号之和(包括起始玩家和每次接球的玩家,同一玩家多次触球则累加多次)。
形式化地:
$$f(x) = x + \text{receiver}[x] + \text{receiver}[\text{receiver}[x]] + \dots + \text{receiver}^{(k)}[x]
$$
其中 receiver(t)[x] 表示从 x 出发经过 t 次传球后接球的玩家编号。
你的任务是选择一个起始玩家 x,使得 f(x) 最大,并输出这个最大值。
【输入格式】
第一行两个整数 n,k,分别表示玩家数量和传球次数。
第二行 n 个整数,第 i 个整数表示 receiver[i](0≤receiver[i]≤n−1)。
【输出格式】
一个整数,表示最大的 f(x)。
【样例 1】
3 4
2 0 1
6
【样例 1 解释】
从玩家 2 开始:
-
第 0 次(初始):接触玩家 2,和 =2
-
第 1 次传球:2 传给 1,和 =2+1=3
-
第 2 次传球:1 传给 0,和 =3+0=3
-
第 3 次传球:0 传给 2,和 =3+2=5
-
第 4 次传球:2 传给 1,和 =5+1=6
所以 f(2)=6,可以证明这是最大值。
【样例 2】
5 3
1 1 1 2 3
10
【样例解释2】
从玩家 4 开始:
-
第 0 次(初始):接触玩家 4,和 =4
-
第 1 次传球:4 传给 3,和 =4+3=7
-
第 2 次传球:3 传给 2,和 =7+2=9
-
第 3 次传球:2 传给 1,和 =9+1=10
所以 f(4)=10,可以证明这是最大值。
【数据规模与约定】
保证 100% 的数据满足:
- 1≤n≤105
- 1≤k≤1010
- 0≤receiver[i]≤n−1