# CF1405D「Tree Tag」

## 1. 题目

### DESCRIPTION

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

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

The first line of each test case contains five integers $n,a,b,da,db$ ($2 \leq n \leq 10^5; 1 \leq a,b \leq n; a \neq b; 1 \leq da,db \leq 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 \leq u, v \leq n, u \neq 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

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

## 2. 题解

### 分析

• $(a,b) \leq da$，则由于 Alice 先手故第一步 Alice 就追上了 Bob，Alice 赢。

• $diameter \leq 2 \times da$，则 Alice 可以先移动到树的中间位置，使得 Alice 下一步可以移动到整棵树的任意一个结点。易知无论 Bob 怎么逃，Alice 移动两步一定可以追上，Alice 赢。

• $2 \times da \lt db$，由于此时 $(a,b) > da$$diameter \gt 2 \times da$，故 Alice 移动后 Bob 还有逃的机会，则 Bob 可以如此应对：

1. 如果 Alice 下一步可以移动到 Bob 当前结点位置，则 Bob 应该以 db 步长移动到树的直径上的某点，此时由于 $2 \times da \lt db$ 故下一步 Alice 追不上 Bob 。
2. 如果 Alice 下一步追不上 Bob，则 Bob 只需待在原位即可。
• $2 \times da \geq db$，Alice 可以采取如下策略获胜：
1. 若下一步无法追上 Bob，则以 $a$ 为树根， Alice 朝 Bob 所在子树方向前进 1 步。如果 Bob 下一步逃离当前子树，则 Bob 移动的路径一定会经过 $a$，则 Bob 无法逃离 $a$ 外大于 $da$ 的距离（因为当前 $(a,b) \geq da$）。
2. 若下一步能够追上 Bob，则 Alice
直接追上即可。