Tree Tag
Contest: Codeforces Round 668 (Div. 1)
Difficulty rating: 1900
Tags: dfs and similar, dp, games, trees

Alice and Bob are playing a fun game of tree tag.

The game is played on a tree of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. Recall that a tree on $$$n$$$ vertices is an undirected, connected graph with $$$n-1$$$ edges.

Initially, Alice is located at vertex $$$a$$$, and Bob at vertex $$$b$$$. They take turns alternately, and Alice makes the first move. In a move, Alice can jump to a vertex with distance at most $$$da$$$ from the current vertex. And in a move, Bob can jump to a vertex with distance at most $$$db$$$ from the current vertex. The distance between two vertices is defined as the number of edges on the unique simple path between them. In particular, either player is allowed to stay at the same vertex in a move. Note that when performing a move, a player only occupies the starting and ending vertices of their move, not the vertices between them.

If after at most $$$10^{100}$$$ moves, Alice and Bob occupy the same vertex, then Alice is declared the winner. Otherwise, Bob wins.

Determine the winner if both players play optimally.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). Description of the test cases follows.

The first line of each test case contains five integers $$$n,a,b,da,db$$$ ($$$2\le n\le 10^5$$$, $$$1\le a,b\le n$$$, $$$a\ne b$$$, $$$1\le da,db\le n-1$$$)  — the number of vertices, Alice's vertex, Bob's vertex, Alice's maximum jumping distance, and Bob's maximum jumping distance, respectively.

The following $$$n-1$$$ lines describe the edges of the tree. The $$$i$$$-th of these lines contains two integers $$$u$$$, $$$v$$$ ($$$1\le u, v\le n, u\ne v$$$), denoting an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that these edges form a tree structure.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output a single line containing the winner of the game: "Alice" or "Bob".

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

Note:
In the first test case, Alice can win by moving to vertex $$$1$$$. Then wherever Bob moves next, Alice will be able to move to the same vertex on the next move.

In the second test case, Bob has the following strategy to win. Wherever Alice moves, Bob will always move to whichever of the two vertices $$$1$$$ or $$$6$$$ is farthest from Alice.

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

Example output:
Alice
Bob
Alice
Alice

Editorial:
Let's consider several cases independently.
Case 1: $$$\mathrm{dist}(a, b)\le da$$$
Unsurprisingly, Alice wins in this case by tagging Bob on the first move.
Case 2: $$$2da\ge \mathrm{tree\ diameter}$$$
Here, the diameter of a tree is defined as the length of the longest simple path.
In this case, Alice can move to a center of the tree. Once Alice is there, it doesn't matter where Bob is, since Alice can reach any vertex in the tree in just one move, winning the game.
Case 3: $$$db > 2da$$$
In this case, let's describe a strategy for Bob to win. Because we are not in case 1, Bob will not lose before his first move. Then it is sufficient to show that Bob can always end his turn with distance greater than $$$da$$$ from Alice.
Since we are not in case 2, there is at least one vertex with distance at least $$$da$$$ from Alice. If Bob is at such a vertex at the start of his turn, he should simply stay there. Otherwise, there is some vertex $$$v$$$ with $$$\mathrm{dist}(a,v)=da+1$$$. Then $$$\mathrm{dist}(b,v)\le \mathrm{dist}(b,a)+\mathrm{dist}(a,v)\le da+(da+1)=2da+1\le db$$$, so Bob can jump to $$$v$$$ on his turn.
Case 4: $$$db \le 2da$$$
In this case, Alice's strategy will be to capture Bob whenever possible or move one vertex closer to Bob otherwise. Let's prove that Alice will win in a finite number of moves with this strategy.
Let's root the tree at $$$a$$$. Bob is located in some subtree of $$$a$$$, say with $$$k$$$ vertices. Alice moves one vertex deeper, decreasing Bob's subtree size by at least one vertex. Since $$$db\le 2da$$$, Bob cannot move to another subtree without being immediately captured, so Bob must stay in this shrinking subtree until he meets his inevitable defeat.
Solution
The only non-trivial part in the implementation is checking for cases $$$1$$$ and $$$2$$$. Case $$$1$$$ is simply checked with DFS. Case 2 only requires computing the diameter of the tree, which is a standard problem.
Complexity is $$$O(n)$$$.