Tree Tag (Codeforces 1405D)
Tags: Others, games

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 \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: For each test case, output a single line containing the winner of the game: "Alice" or "Bob".

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.  

Sample Inputs:
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

Sample Outputs:
Alice
Bob
Alice
Alice

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, a, b, da, db) = readInts()
    graph = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = readInts()
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)
    if da > db:
        return 'Alice'
    qu = deque([(a - 1, 0)])
    marked = [False] * n
    marked[a - 1] = True
    while qu:
        (node, d) = qu.popleft()
        if node == b - 1 and d <= da:
            return 'Alice'
        for nei in graph[node]:
            if not marked[nei]:
                marked[nei] = True
                qu.append((nei, d + 1))
    depth = [0] * n
    st = [(0, 0)]
    par = [-1] * n
    par[0] = -2
    while st:
        (node, marked) = st.pop()
        if marked:
            if node > 0:
                depth[par[node]] = max(depth[par[node]], 1 + depth[node])
        else:
            st.append((node, 1))
            for nei in graph[node]:
                if par[nei] == -1:
                    par[nei] = node
                    st.append((nei, 0))
    st = [0]
    d1 = [0] * n
    d2 = [0] * n
    while st:
        node = st.pop()
        if node > 0:
            p = par[node]
            d2[node] = 1 + d2[p]
            for nei in graph[p]:
                if nei != node and par[nei] == p:
                    d1[node] = max(d1[node], 2 + depth[nei])
                    d2[node] = max(d2[node], 2 + depth[nei])
        for nei in graph[node]:
            if par[nei] == node:
                st.append(nei)
    for i in range(n):
        if max(d2[i], depth[i], d1[i]) <= da:
            return 'Alice'
    return 'Bob' if 2 * da + 1 <= db else 'Alice'
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, a, b, da, db) = readInts()
    graph = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = readInts()
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)
    qu = deque([(a - 1, 0)])
    marked = [False] * n
    marked[a - 1] = True
    (dis, v1) = (0, a - 1)
    while qu:
        (node, d) = qu.popleft()
        if d > dis:
            dis = d
            v1 = node
        if node == b - 1 and d <= da:
            return 'Alice'
        for nei in graph[node]:
            if not marked[nei]:
                marked[nei] = True
                qu.append((nei, d + 1))
    qu = deque([(v1, 0)])
    marked = [False] * n
    marked[v1] = True
    dia = 0
    while qu:
        (node, d) = qu.popleft()
        dia = max(dia, d)
        for nei in graph[node]:
            if not marked[nei]:
                qu.append((nei, d + 1))
                marked[nei] = True
    return 'Bob' if 2 * da < db and dia > 2 * da else 'Alice'
for _ in range(int(input())):
    print(solve())

Solution (Python):
from sys import stdin

class Problem:

    def __init__(self, n, a, b, da, db, e):
        self.n = n
        self.a = a - 1
        self.b = b - 1
        self.da = da
        self.db = db
        self.g = [[] for i in range(n)]
        for (u, v) in e:
            self.g[u - 1].append(v - 1)
            self.g[v - 1].append(u - 1)

    def dfs(self, v, dist=0):
        self.d[v] = dist
        for u in self.g[v]:
            if self.d[u] == None:
                self.dfs(u, dist + 1)

    def solve(self):
        if self.da * 2 >= self.db:
            return 'Alice'
        self.d = [None for i in range(self.n)]
        self.dfs(self.a)
        if self.d[self.b] <= self.da:
            return 'Alice'
        f = self.d.index(max(self.d))
        self.d = [None for i in range(self.n)]
        self.dfs(f)
        d = max(self.d)
        if self.da * 2 >= d:
            return 'Alice'
        return 'Bob'

def test_cases():
    cases = int(stdin.readline())
    for case in range(cases):
        (n, a, b, da, db) = list(map(int, stdin.readline().split()))
        e = [list(map(int, stdin.readline().split())) for i in range(n - 1)]
        yield Problem(n, a, b, da, db, e)
for test in test_cases():
    ans = test.solve()
    print(ans)