| Codeforces Round 973 (Div. 2) |
|---|
| Закончено |
Это сложная версия задачи. В этой версии не гарантируется, что $$$u = v$$$. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Алиса и Боб играют в забавную игру на дереве. В эту игру играют на дереве из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Напомним, что дерево на $$$n$$$ вершинах — это неориентированный связный граф с $$$n - 1$$$ ребрами.
Алиса и Боб ходят по очереди, причём Алиса ходит первой. Каждый игрок начинает с какой-то вершины.
В свой ход игрок должен перейти из текущей вершины в соседнюю вершину, которая ещё не была никем посещена до этого. Первый игрок, который не может сделать ход, проигрывает.
Вам даны две вершины $$$u$$$ и $$$v$$$. Представим простой путь из вершины $$$u$$$ в $$$v$$$ как массив $$$p_1, p_2, p_3, \ldots, p_m$$$, где $$$p_1 = u$$$, $$$p_m = v$$$, между $$$p_i$$$ и $$$p_{i + 1}$$$ есть ребро для всех $$$i$$$ ($$$1 \le i < m$$$).
Вы должны определить победителя игры, если Алиса начнёт в вершине $$$1$$$, а Боб в вершине $$$p_j$$$ для каждого $$$j$$$ (где $$$1 \le j \le m$$$).
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество вершин дерева.
Каждая из следующих $$$n - 1$$$ строк содержит два целых числа $$$a$$$, $$$b$$$ ($$$1 \le a, b \le n$$$), обозначающих неориентированное ребро между вершинами $$$a$$$ и $$$b$$$. Гарантируется, что данные рёбра образуют дерево.
Последняя строка каждого набора входных данных содержит два целых числа $$$u$$$ и $$$v$$$ ($$$2 \le u, v \le n$$$).
Гарантируется, что путь между $$$u$$$ и $$$v$$$ не проходит через вершину $$$1$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$m$$$ строк.
В $$$i$$$-й строке выведите победителя игры, если Алиса начинает с вершины $$$1$$$, а Боб с вершины $$$p_i$$$, выведите «Alice» (без кавычек), если выиграет Алиса, или «Bob» (без кавычек) в противном случае.
331 22 32 361 21 32 42 51 64 541 21 32 42 4
Bob Alice Alice Bob Alice Bob Alice
Дерево из первого примера. В первом наборе входных данных путь будет иметь вид ($$$2,3$$$). В случае, когда Боб начинает в вершине $$$2$$$, Алиса в своём первом ходу не сможет никуда пойти, и она проиграет.
А в случае, когда Боб начинает в вершине $$$3$$$, Алиса переместится в вершину $$$2$$$, и у Боба не останется вершин, которые можно посетить, и он проиграет.
