Tree and Permutation Game
Contest: Codeforces Round 782 (Div. 2)
Difficulty rating: 3000
Tags: dfs and similar, games, graphs, trees

There is a tree of $$$n$$$ vertices and a permutation $$$p$$$ of size $$$n$$$. A token is present on vertex $$$x$$$ of the tree.

Alice and Bob are playing a game. Alice is in control of the permutation $$$p$$$, and Bob is in control of the token on the tree. In Alice's turn, she must pick two distinct numbers $$$u$$$ and $$$v$$$ (not positions; $$$u \neq v$$$), such that the token is neither at vertex $$$u$$$ nor vertex $$$v$$$ on the tree, and swap their positions in the permutation $$$p$$$. In Bob's turn, he must move the token to an adjacent vertex from the one it is currently on.

Alice wants to sort the permutation in increasing order. Bob wants to prevent that. Alice wins if the permutation is sorted in increasing order at the beginning or end of her turn. Bob wins if he can make the game go on for an infinite number of moves (which means that Alice is never able to get a sorted permutation). Both players play optimally. Alice makes the first move.

Given the tree, the permutation $$$p$$$, and the vertex $$$x$$$ on which the token initially is, find the winner of the game.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$)  — the number of test cases. The description of each test case follows.

The first line of each test case has two integers $$$n$$$ and $$$x$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq x \leq n$$$).

Each of the next $$$n-1$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \neq b$$$) indicating an undirected edge between vertex $$$a$$$ and vertex $$$b$$$. It is guaranteed that the given edges form a tree.

The next line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$)  — the permutation $$$p$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output one line containing Alice or Bob — the winner of the game. The output is case-sensitive.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Here is the explanation for the first example:

In the first test case, there is a way for Alice to win. Here is a possible sequence of moves:

1. Alice swaps $$$5$$$ and $$$6$$$, resulting in $$$[2,1,3,5,4,6]$$$.
2. Bob moves the token to vertex $$$5$$$.
3. Alice swaps $$$1$$$ and $$$2$$$, resulting in $$$[1,2,3,5,4,6]$$$.
4. Bob moves the token to vertex $$$3$$$.
5. Alice swaps $$$4$$$ and $$$5$$$, resulting in $$$[1,2,3,4,5,6]$$$, and wins.

In the second test case, Alice cannot win since Bob can make the game go on forever. Here is the sequence of moves:

1. Alice can only swap $$$1$$$ and $$$3$$$, resulting in $$$[3,1,2]$$$.
2. Bob moves the token to vertex $$$1$$$.
3. Alice can only swap $$$2$$$ and $$$3$$$, resulting in $$$[2,1,3]$$$.
4. Bob moves the token to vertex $$$2$$$.
5. Alice can only swap $$$1$$$ and $$$3$$$, resulting in $$$[2,3,1]$$$.
6. Bob moves the token to vertex $$$3$$$.
7. Alice can only swap $$$1$$$ and $$$2$$$, resulting in $$$[1,3,2]$$$.
8. Bob moves the token to vertex $$$2$$$.

In the third test case, Alice wins immediately since the permutation is already sorted.

Example input:
3
6 3
1 3
3 2
4 3
3 6
5 3
2 1 3 6 4 5
3 2
1 2
3 2
1 3 2
3 2
1 2
3 2
1 2 3

Example output:
Alice
Bob
Alice

Example input:
1
11 4
3 11
5 9
10 3
4 8
2 4
1 8
6 8
8 7
4 5
5 11
7 4 9 8 6 5 11 10 2 3 1

Example output:
Alice

Editorial:
Let us call all such $$$i$$$ that satisfy $$$p_i \neq i$$$ as marked. If $$$p_i=i$$$, it is called unmarked. Also, a notation like $$$XY$$$ means "swap $$$X$$$ and $$$Y$$$ in the permutation".
We are going to show that it is always possible for Alice to win if the diameter of the tree is $$$\geq 3$$$.
First of all, it should be obvious that no matter what moves are made, we will eventually end up at a state where we have just $$$2$$$ marked vertices and the token is either on one of them or neither of them (with Alice having to move). In the latter case we have a trivial win.
Proof:
As long as there are $$$>2$$$ marked numbers, you can always find a pair of numbers to swap that will unmark one of the numbers. One can imagine this in terms of the cycle decomposition of the permutation.
—————
Next, let us show that from the former state, we can also force a state where the two marked vertices are adjacent to each other (with Alice having to move).
Proof:
If the two marked vertices are already adjacent, we don't need to do anything. Else, let's say we have $$$A$$$ and $$$B$$$ where $$$B$$$ is the vertex with the token on it. Now, consider two cases. If $$$A$$$ is at distance $$$\geq 3$$$ from $$$B$$$, we can choose any adjacent vertex to $$$B$$$. Let it be $$$C$$$. Swap $$$C$$$ and $$$A$$$. Now Bob has the option of moving the token onto $$$C$$$ or not. It wouldn't be optimal to move it away from $$$C$$$, because then we can force the sequence $$$BC$$$ $$$CA$$$ and Bob won't be able to cover any vertex with his token. So Bob must move his token onto $$$C$$$. Swap $$$A$$$ and $$$B$$$, which puts $$$A$$$ in its right place. Now Bob must move this token onto $$$B$$$, so we did it. If $$$A$$$ is instead at distance $$$2$$$ from $$$B$$$, pick the vertex between $$$B$$$ and $$$A$$$ as $$$C$$$, and we can repeat the same analysis as above.
—————
Now, let's say we have $$$A$$$ and $$$B$$$ with $$$B$$$ being the vertex with the token on it. Let us show that, if possible, we can always move $$$A$$$ over $$$B$$$ and $$$B$$$ over $$$A$$$ (effectively "jumping" over the opposite vertex).
Proof:
For the first one, pick some vertex adjacent to $$$B$$$ (not $$$A$$$). Let it be $$$C$$$. Swap $$$A$$$ and $$$C$$$. Now Bob has the option of moving to either $$$C$$$ or $$$A$$$. If he moves to $$$A$$$, we can force $$$BC$$$ $$$CA$$$ and win. If he moves to $$$C$$$, we swap $$$AB$$$ (putting $$$A$$$ in the right place) and Bob has to move his token to $$$B$$$. Now we can see that the marked vertex which was $$$A$$$, "jumped" over $$$B$$$ to reach $$$C$$$.
For the second one, pick some vertex adjacent to $$$A$$$ (not $$$B$$$). Let it be $$$C$$$. Bob must move his token to $$$A$$$. Swap $$$B$$$ and $$$C$$$ (putting $$$B$$$ in the right place). Bob must move his token to $$$C$$$. Now we can see that the marked vertex with a token which was $$$B$$$, "jumped" over $$$A$$$ to reach $$$C$$$.
—————
Like this, we can move all over the tree. Now let's move such that both of the marked vertices lie on a diameter of the tree and one of them is at one end of it.
Consider a tree with diameter $$$\geq 3$$$. That means we have a line of at least $$$4$$$ vertices taking the two marked vertices at one end. Let's consider just the first $$$4$$$ vertices, and show that we can always win here.
Proof:
Say we have a configuration like $$$A$$$-$$$B$$$-$$$C$$$-$$$D$$$ where $$$A$$$ and $$$B$$$ are marked and $$$A$$$ has the token on it. If $$$B$$$ has the token on it instead, we can use the moving strategy explained before to first move $$$A$$$ to $$$C$$$ and then $$$B$$$ to $$$D$$$ and then it is equivalent to the first configuration. Swap $$$B$$$ and $$$D$$$. Now Bob must move his token to $$$B$$$. Swap $$$A$$$ and $$$D$$$ (putting $$$A$$$ in its right place). Now no matter where Bob moves, after his turn no vertex will be covered and we can force $$$BD$$$ and win.
—————
Therefore, if the diameter of the tree is $$$\geq 3$$$, we always win.
If the diameter of the tree is $$$2$$$, it is a star graph, and this is a more problematic case.
First of all, we must check if the permutation is already sorted, or we can win in the first move. We can only win in the first move if only $$$1$$$ swap is required to sort the permutation, and the token is on neither of the numbers we need to swap.
If the above is not possible, several cases follow.
Let us make the following observation first. If Bob is at the center of the star and the center is a marked vertex, Bob can infinitely stall Alice.
Proof:
Let's call the center $$$A$$$, and suppose we need to swap the number $$$B$$$ with it to put it in its right place. $$$B$$$ is definitely at a leaf and $$$1$$$ vertex away because of the structure of the star graph. So when Bob's turn comes he can simply move the token to where $$$B$$$ is and alternate this way between $$$A$$$ and $$$B$$$, infinitely stalling Alice. Obviously, even if we try swapping $$$B$$$ with a different number $$$C$$$, we can just move to where $$$C$$$ is next until there are just two vertices left, the center and a leaf. So Bob wins.
—————
In light of this, it never makes sense to mark the center in our turn if it is unmarked and not covered by the token.
So we have $$$4$$$ cases to think of now:
- Token on center and center is marked vertex: As explained before, Alice loses here.
Before discussing the rest of the cases, let us define $$$d$$$ as the minimum number of swaps required to sort the permutation and $$$x$$$ is $$$0$$$ if the token is on the center and $$$1$$$ if it is on a leaf.
Now I claim that the parity of $$$d+x$$$ is invariant. The magnitude of $$$x$$$ changes by exactly $$$1$$$ every turn and we can say the same about $$$d$$$. So considering all possible changes ($$$-1$$$,$$$-1$$$) ($$$-1$$$,$$$+1$$$) ($$$+1$$$,$$$-1$$$) ($$$+1$$$,$$$+1$$$) we can see the sum of the changes is always $$$0 \bmod 2$$$. Hence proved.
Consider the possible end states for the game: (all with $$$2$$$ marked vertices and with Alice having to move)
1. Token at center, center marked
2. Token at unmarked leaf, center marked
3. Token at marked leaf, center marked
4. Token at center, center unmarked
5. Token at unmarked leaf, center unmarked
6. Token at marked leaf, center unmarked
Observe that end states $$$2$$$ and $$$5$$$ will never occur if the game lasts longer than $$$1$$$ turn because if you go back by $$$1$$$ turn, Bob would have a more optimal move. Therefore, in states $$$2$$$ and $$$5$$$ we can win in the very first move. Further observe that states $$$1$$$ and $$$2$$$ will never occur if the center was initially unmarked or we could unmark it in the first move. The only other possibility would be us being unable to unmark the center in the first move, which is a losing state. So we only care about states $$$4$$$ and $$$6$$$ now.
Observe that state $$$4$$$ is a winning position while state $$$6$$$ is a losing position. Also observe that state $$$4$$$ has $$$d+x$$$ odd but state $$$6$$$ has $$$d+x$$$ even. Now let us continue with the cases and use these facts.
- Token at center and center is unmarked vertex: Check the parity of $$$d+x$$$ here. If it is odd, we win, otherwise we lose (follows from the invariance of $$$d+x$$$).
- Token at leaf and center is marked vertex: If we cannot unmark the center vertex in our very first move, we'll reach a losing position. If we can, check parity of $$$d+x$$$. Odd is win, even is lose. When can we not unmark the center vertex? Only if the token is on $$$p_{center}$$$. Otherwise it is always possible.
- Token at leaf and center is unmarked vertex: Check parity of $$$d+x$$$. Odd is win, even is lose.
This completes the solution.
Time complexity: $$$\mathcal{O}(n)$$$ or $$$\mathcal{O}(n\log{n})$$$ (depending on whether you use cycles or inversions to find the parity of $$$d$$$)