AT_abc148_f [ABC148F] Playing Tag on Tree

题目描述

有一棵包含 $N$ 个顶点的树。第 $i$ 条边连接了顶点 $A_i$ 和 $B_i$，且为双向边。

高桥君在顶点 $u$，青木君在顶点 $v$。

两人按照如下规则进行“捉迷藏”游戏：

• 1. 如果高桥君和青木君在同一个顶点，游戏结束。否则，高桥君选择一个相邻的顶点并移动到该顶点。
• 2. 如果高桥君和青木君在同一个顶点，游戏结束。否则，青木君选择一个相邻的顶点并移动到该顶点。
• 3. 回到步骤 1。

高桥君会尽可能让游戏结束得更晚，而青木君会尽可能让游戏结束得更早。

假设两人始终知道对方的位置和策略，并且都采取最优行动，求在游戏结束前，青木君移动的次数。

已知游戏一定会结束。

输入格式

输入以如下格式从标准输入读入：

$N$ $u$ $v$ $A_1$ $B_1$ $:$ $A_{N-1}$ $B_{N-1}$

输出格式

输出游戏结束前青木君移动的次数。

样例 1

输入

5 4 1
1 2
2 3
3 4
3 5

输出

2

样例 2

输入

5 4 5
1 2
1 3
1 4
1 5

输出

1

样例 3

输入

2 1 2
1 2

输出

0

样例 4

输入

9 6 1
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 9

输出

5

说明/提示

限制条件

• $2 \leq N \leq 10^5$
• $1 \leq u, v \leq N$
• $u \neq v$
• $1 \leq A_i, B_i \leq N$
• 给定的图是一棵树

样例说明 1

在双方都采取最优策略的情况下，游戏的过程如下：

• 高桥君移动到顶点 $3$
• 青木君移动到顶点 $2$
• 高桥君移动到顶点 $5$
• 青木君移动到顶点 $3$
• 高桥君移动到顶点 $3$

此时，青木君在游戏结束前共移动了 $2$ 次。

注意，每一回合都不能停留在原地。

由 ChatGPT 4.1 翻译