Moving Piece

题目描述

Takahashi 将在编号为 $1, 2, \cdots, 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$

输出格式

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

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

8

2 3
2 1
10 -7

13

3 3
3 1 2
-1000 -2000 -3000

-1000

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

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$，此时得分为 $4$。再进行一次移动会将棋子送到格子 $4$，此时得分为 $4 + (-8) = -4$。 如果我们从格子 $2$ 开始，进行一次移动会将棋子送到格子 $4$，此时得分为 $-8$。再进行一次移动会将棋子送到格子 $1$，此时得分为 $-8 + 3 = -5$。 如果我们从格子 $3$ 开始，进行一次移动会将棋子送到格子 $5$，此时得分为 $8$。再进行一次移动会将棋子送到格子 $3$，此时得分为 $8 + (-10) = -2$。 如果我们从格子 $4$ 开始，进行一次移动会将棋子送到格子 $1$，此时得分为 $3$。再进行一次移动会将棋子送到格子 $2$，此时得分为 $3 + 4 = 7$。 如果我们从格子 $5$ 开始，进行一次移动会将棋子送到格子 $3$，此时得分为 $-10$。再进行一次移动会将棋子送到格子 $5$，此时得分为 $-10 + 8 = -2$。

能够达到的最大得分是 $8$.
我们必须至少进行一次移动。
答案的绝对值可能很大。

标签: AtCoder|abc175D

来源

AtCoder|abc175D