CF1659F Tree and Permutation Game

有一棵包含 $n$ 个顶点的树，以及一个长度为 $n$ 的排列 $p$。树上的某个顶点 $x$ 上有一个棋子。 Alice 和 Bob 正在玩一个游戏。Alice 控制排列 $p$，Bob 控制树上的棋子。Alice 的回合，她必须选择两个不同的数字 $u$ 和 $v$（不是位置，$u \neq v$），并且树上的棋子当前不在顶点 $u$ 或 $v$ 上，然后交换 $p$ 中 $u$ 和 $v$ 的位置。Bob 的回合，他必须将棋子移动到与当前位置相邻的顶点。 Alice 的目标是将排列按升序排序。Bob 的目标是阻止 Alice 达成目标。如果在 Alice 的回合开始或结束时，排列已经升序排序，则 Alice 获胜。如果 Bob 能让游戏无限进行下去（即 Alice 永远无法将排列排好序），则 Bob 获胜。两人都采取最优策略。Alice 先手。 给定树的结构、排列 $p$ 以及棋子初始所在的顶点 $x$，请判断谁会获胜。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。每个测试用例的描述如下。 每个测试用例的第一行包含两个整数 $n$ 和 $x$（$3 \leq n \leq 2 \cdot 10^5$；$1 \leq x \leq n$）。 接下来的 $n-1$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le n$，$a \neq b$），表示树上的一条无向边。保证这些边构成一棵树。 接下来一行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$），表示排列 $p$。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行，内容为 Alice 或 Bob，表示游戏的获胜者。输出需区分大小写。

以下是第一个样例的解释： 在第一个测试用例中，Alice 有办法获胜。以下是可能的操作序列： 1. Alice 交换 $5$ 和 $6$，得到 $[2,1,3,5,4,6]$。 2. Bob 将棋子移动到顶点 $5$。 3. Alice 交换 $1$ 和 $2$，得到 $[1,2,3,5,4,6]$。 4. Bob 将棋子移动到顶点 $3$。 5. Alice 交换 $4$ 和 $5$，得到 $[1,2,3,4,5,6]$，Alice 获胜。 在第二个测试用例中，Alice 无法获胜，因为 Bob 可以让游戏无限进行。以下是操作序列： 1. Alice 只能交换 $1$ 和 $3$，得到 $[3,1,2]$。 2. Bob 将棋子移动到顶点 $1$。 3. Alice 只能交换 $2$ 和 $3$，得到 $[2,1,3]$。 4. Bob 将棋子移动到顶点 $2$。 5. Alice 只能交换 $1$ 和 $3$，得到 $[2,3,1]$。 6. Bob 将棋子移动到顶点 $3$。 7. Alice 只能交换 $1$ 和 $2$，得到 $[1,3,2]$。 8. Bob 将棋子移动到顶点 $2$。 然后这个过程会无限循环。 在第三个测试用例中，排列已经有序，Alice 立即获胜。 由 ChatGPT 4.1 翻译