CF1405D「Tree Tag」

1. 题目

题目链接：CF1405D「Tree Tag」 。

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 dadada from the current vertex. And in a move, Bob can jump to a vertex with distance at most dbfrom 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”.

Example

Input #1

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

Output #2

Alice
Bob
Alice
Alice

2. 题解

分析

题目描述感觉有点诘屈聱牙，这个问题主要就是说如果在有限步骤内，Alice 和 Bob 能够同时移动到同一个顶点上，那么 Alice 赢；否则 Bob 赢。就相当于 Bob 逃，Alice 追，追得上 Alice 赢，追不上 Bob 赢。这道题蒟蒻的我也是看了官方题解才弄懂的（Orz）。

对于这道题应该分情况讨论：设树中 a 到 b 的唯一简单路径长度为 (a,b)，树的直径为 diameterdiameterdiameter，则

• 若 (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 直接追上即可。

代码

#include <bits/stdc++.h>
#define ll int
#define MAXN 100005
using namespace std;

// 前向星存边
ll cnt;
ll head[MAXN];
struct edge{
    ll to, next;
}e[2*MAXN];
void init() {
    cnt = 0;
    memset(head, -1, sizeof(head));
}
void addEdge(ll u, ll v) {
    e[cnt].next = head[u];
    e[cnt].to = v;
    head[u] = cnt++;
    e[cnt].next = head[v];
    e[cnt].to = u;
    head[v] = cnt++;
}

ll dia;
ll vis[MAXN];
ll depth[MAXN];
vector <ll> v[MAXN];
// dfs 求出树的直径
// 同时求出 a 和 b 的距离
ll dfs(ll a, ll b) {
    vis[a] = 1;
    ll res = 0;
    v[a].clear();
    for(ll i = head[a]; i != -1; i = e[i].next) {
        ll u = e[i].to;
        if(!vis[u]) {
            depth[u] = depth[a] + 1;
            res = dfs(u, b);
            v[a].push_back(res+1);
        }
    }
    if(v[a].size()) {
        sort(v[a].begin(),v[a].end(), greater<ll>());
        if(v[a].size() > 1) {
            dia = max(dia, v[a][0]+v[a][1]);
        } else {
            dia = max(dia, v[a][0]);
        }
        res = v[a][0];
    }
    return res;
}


int main()
{
    ll t;
    scanf("%d", &t);
    for(ll i = 0; i < t; ++i) {
        ll n, a, b, da, db;
        init();
        scanf("%d%d%d%d%d", &n, &a, &b, &da, &db);
        for(ll j = 0; j < n-1; ++j) {
            ll u, v;
            scanf("%d%d", &u, &v);
            addEdge(u, v);
        }
        bool mark;
        dia = 0;
        memset(vis, 0, sizeof(vis));
        memset(depth, 0, sizeof(depth));
        dfs(a, b);
        ll dist = depth[b];
        if(dist <= da) {
            mark = true;
        } else if(dia <= 2*da) {
            mark = true;
        } else if(2*da < db) {
            mark = false;
        } else {
            mark = true;
        }
        printf("%s\n", mark ? "Alice" : "Bob");
    }
    return 0;
}