CF2013F2 Game in Tree (Hard Version)

这是问题的困难版本。在这一版本中，不要求 $u = v$。只有当两个版本的问题都成功解决后，你才能进行 hack。 Alice 和 Bob 在一棵树上玩一个有趣的游戏。这棵树有 $n$ 个顶点，编号从 $1$ 到 $n$。回顾一下，一棵有 $n$ 个顶点的树是一个有 $n - 1$ 条边的无向连通图。 游戏规则是 Alice 和 Bob 轮流移动，Alice 先行动，每位玩家在自己的回合中，必须从当前所在的顶点移动到一个尚未被访问过的相邻顶点。如果某个玩家无法移动，则他输掉比赛。 给定两个顶点 $u$ 和 $v$。从顶点 $u$ 到顶点 $v$ 的简单路径用数组表示为 $p_1, p_2, p_3, \ldots, p_m$，其中 $p_1 = u$，$p_m = v$，并且每对相邻的顶点 $p_i$ 和 $p_{i+1}$之间都有一条边（$1 \le i < m$）。 你的任务是，判断在 Alice 从顶点 $1$ 开始，而 Bob 从路径中的顶点 $p_j$（$1 \le j \le m$）开始的情况下，谁将获胜。

无

无

在第一个例子中，路径是（$2, 3$）。如果 Bob 开始时位于顶点 $2$，Alice 在第一回合就无法移动，只能输掉比赛。而如果 Bob 从顶点 $3$ 开始，Alice 会移动到顶点 $2$，此时 Bob 就没有顶点可动并会输掉比赛。 **本翻译由 AI 自动生成**