AT_abc175_d [ABC175D] Moving Piece

题目描述

高桥君打算在由编号为 $1, 2, \cdots, N$ 的 $N$ 个格子组成的棋盘上，用棋子玩一个游戏。每个格子 $i$ 上写有一个整数 $C_i$。此外，还给定了一个 $1, 2, \cdots, N$ 的排列 $P_1, P_2, \cdots, P_N$。

接下来，高桥君可以任选一个格子放置一个棋子，并且可以选择移动棋子的次数，次数不少于 $1$ 次且不超过 $K$ 次。每次移动的规则如下：

• 每次移动时，若棋子当前在格子 $i$（$1 \leq i \leq N$），则将棋子移动到格子 $P_i$。此时，分数会增加 $C_{P_i}$。

请你帮高桥君求出，游戏结束时可能获得的最大分数是多少。（游戏开始时分数为 $0$。）

输入格式

输入按以下格式从标准输入读入。

$N$ $K$
$P_1$ $P_2$ $\cdots$ $P_N$
$C_1$ $C_2$ $\cdots$ $C_N$

输出格式

输出游戏结束时可能获得的最大分数。

输入输出样例 #1

输入 #1

5 2
2 4 5 1 3
3 4 -10 -8 8

输出 #1

8

输入输出样例 #2

输入 #2

2 3
2 1
10 -7

输出 #2

13

输入输出样例 #3

输入 #3

3 3
3 1 2
-1000 -2000 -3000

输出 #3

-1000

输入输出样例 #4

输入 #4

10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719

输出 #4

29507023469

说明/提示

限制条件

• $2 \leq N \leq 5000$
• $1 \leq K \leq 10^9$
• $1 \leq P_i \leq N$
• $P_i \neq i$
• $P_1, P_2, \cdots, P_N$ 互不相同
• $-10^9 \leq C_i \leq 10^9$
• 输入均为整数

样例解释 1

任选一个格子开始，最多移动 $2$ 次的方案如下：

• 初始在格子 $1$。移动 $1$ 次到格子 $2$，分数为 $4$。移动 $2$ 次到格子 $4$，分数为 $4 + (-8) = -4$。
• 初始在格子 $2$。移动 $1$ 次到格子 $4$，分数为 $-8$。移动 $2$ 次到格子 $1$，分数为 $-8 + 3 = -5$。
• 初始在格子 $3$。移动 $1$ 次到格子 $5$，分数为 $8$。移动 $2$ 次到格子 $3$，分数为 $8 + (-10) = -2$。
• 初始在格子 $4$。移动 $1$ 次到格子 $1$，分数为 $3$。移动 $2$ 次到格子 $2$，分数为 $3 + 4 = 7$。
• 初始在格子 $5$。移动 $1$ 次到格子 $3$，分数为 $-10$。移动 $2$ 次到格子 $5$，分数为 $-10 + 8 = -2$。

这些方案中的最大值为 $8$。

样例解释 3

必须至少移动 $1$ 次棋子。

样例解释 4

答案的绝对值可能会非常大。

由 ChatGPT 4.1 翻译