CF1968D Permutation Game

Bodya 和 Sasha 找到了一组排列 $p_1,\dots,p_n$ 和一个数组 $a_1,\dots,a_n$。他们决定玩一个著名的“排列游戏”。 长度为 $n$ 的排列是一个包含 $n$ 个 $1$ 到 $n$ 的不同整数的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中有 $4$）。 他们两人都选择了一个排列中的起始位置。 游戏持续 $k$ 回合。两位玩家同时进行操作。每一回合，每位玩家会发生两件事： - 如果玩家当前位置为 $x$，他的得分增加 $a_x$。 - 然后，玩家可以选择留在当前位置 $x$，或者从 $x$ 移动到 $p_x$。 在恰好 $k$ 回合后，得分更高的玩家获胜。已知 Bodya 的起始位置为 $P_B$，Sasha 的起始位置为 $P_S$，请判断如果两位玩家都采取最优策略，谁会获胜。

第一行包含一个整数 $t$（$1\le t\le 10^4$）——表示测试用例的数量。 每个测试用例的第一行包含四个整数 $n$、$k$、$P_B$、$P_S$（$1\le P_B,P_S\le n\le 2\cdot 10^5$，$1\le k\le 10^9$）——排列的长度、游戏持续的回合数、两位玩家的起始位置。 接下来一行包含 $n$ 个整数 $p_1,\dots,p_n$（$1 \le p_i \le n$）——排列 $p$ 的元素。 再下一行包含 $n$ 个整数 $a_1,\dots,a_n$（$1\le a_i\le 10^9$）——数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每个测试用例，输出一行： - 如果 Bodya 获胜，输出 "Bodya"； - 如果 Sasha 获胜，输出 "Sasha"； - 如果两人得分相同，输出 "Draw"。

下面是第一个测试用例的解释，其中游戏持续 $k=2$ 回合。 | 回合 | Bodya 位置 | Bodya 得分 | Bodya 操作 | Sasha 位置 | Sasha 得分 | Sasha 操作 | |------|------------|------------|------------|------------|------------|------------| | 第一回合 | $3$ | $0 + a_3 = 0 + 5 = 5$ | 留在原地 | $2$ | $0 + a_2 = 0 + 2 = 2$ | 移动到 $p_2=1$ | | 第二回合 | $3$ | $5 + a_3 = 5 + 5 = 10$ | 留在原地 | $1$ | $2 + a_1 = 2 + 7 = 9$ | 留在原地 | | 最终结果 | $3$ | $10$ | | $1$ | $9$ | | 可以看到，Bodya 的得分更高，因此他赢得了比赛。可以证明，Bodya 总是可以赢得这场比赛。 由 ChatGPT 4.1 翻译