#W1112. 传球游戏

传球游戏

【题目描述】

n n 名玩家,编号为 0,1,,n1 0,1,\dots,n-1 。给定一个长度为 n n 的数组 receiver,其中 receiver[i] 表示玩家 i i 会将球传给玩家 receiver[i](允许传给自己)。 现在你需要选择一名玩家作为起始持球者,然后球会被恰好传递 k k 次。
定义函数 f(x) f(x) 为:从玩家 x x 开始,经过 k k 次传球,所有接触过球的玩家编号之和(包括起始玩家和每次接球的玩家,同一玩家多次触球则累加多次)。
形式化地:

$$f(x) = x + \text{receiver}[x] + \text{receiver}[\text{receiver}[x]] + \dots + \text{receiver}^{(k)}[x] $$

其中 receiver(t)[x]\text{receiver}^{(t)}[x] 表示从 x x 出发经过 t t 次传球后接球的玩家编号。

你的任务是选择一个起始玩家 x x ,使得 f(x) f(x) 最大,并输出这个最大值。

【输入格式】

第一行两个整数 n,k n, k ,分别表示玩家数量和传球次数。
第二行 n n 个整数,第 i i 个整数表示 receiver[i]\text{receiver}[i]0receiver[i]n1 0 \le \text{receiver}[i] \le n-1 )。

【输出格式】

一个整数,表示最大的 f(x)f(x)

【样例 1】

3 4
2 0 1
6

【样例 1 解释】

从玩家 22 开始:

  • 00 次(初始):接触玩家 22,和 =2= 2

  • 11 次传球:22 传给 11,和 =2+1=3= 2+1=3

  • 22 次传球:11 传给 00,和 =3+0=3= 3+0=3

  • 33 次传球:00 传给 22,和 =3+2=5= 3+2=5

  • 44 次传球:22 传给 11,和 =5+1=6= 5+1=6

    所以 f(2)=6 f(2)=6 ,可以证明这是最大值。

【样例 2】

5 3
1 1 1 2 3
10

【样例解释2】

从玩家 44 开始:

  • 00 次(初始):接触玩家 44,和 =4=4

  • 11 次传球:44 传给 33,和 =4+3=7= 4+3=7

  • 22 次传球:33 传给 22,和 =7+2=9= 7+2=9

  • 33 次传球:22 传给 11,和 =9+1=10= 9+1=10

    所以 f(4)=10 f(4)=10 ,可以证明这是最大值。

【数据规模与约定】

保证 100%100\% 的数据满足:

  • 1n105 1 \le n \le 10^5
  • 1k1010 1 \le k \le 10^{10}
  • 0receiver[i]n1 0 \le \text{receiver}[i] \le n-1