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 翻译