A7542. [ABC148F] Playing Tag on Tree
编程题
普及+/提高
知识点
题目描述
有一棵包含 $N$ 个顶点的树。第 $i$ 条边连接了顶点 $A_i$ 和 $B_i$，且为双向边。
高桥君在顶点 $u$，青木君在顶点 $v$。
两人按照如下规则进行“捉迷藏”游戏：
- 1. 如果高桥君和青木君在同一个顶点，游戏结束。否则，高桥君选择一个相邻的顶点并移动到该顶点。
- 2. 如果高桥君和青木君在同一个顶点，游戏结束。否则，青木君选择一个相邻的顶点并移动到该顶点。
- 3. 回到步骤 1。
高桥君会尽可能让游戏结束得更晚，而青木君会尽可能让游戏结束得更早。
假设两人始终知道对方的位置和策略，并且都采取最优行动，求在游戏结束前，青木君移动的次数。
已知游戏一定会结束。
高桥君在顶点 $u$，青木君在顶点 $v$。
两人按照如下规则进行“捉迷藏”游戏：
- 1. 如果高桥君和青木君在同一个顶点，游戏结束。否则，高桥君选择一个相邻的顶点并移动到该顶点。
- 2. 如果高桥君和青木君在同一个顶点，游戏结束。否则，青木君选择一个相邻的顶点并移动到该顶点。
- 3. 回到步骤 1。
高桥君会尽可能让游戏结束得更晚，而青木君会尽可能让游戏结束得更早。
假设两人始终知道对方的位置和策略，并且都采取最优行动，求在游戏结束前，青木君移动的次数。
已知游戏一定会结束。
输入格式
输入以如下格式从标准输入读入：
> $N$ $u$ $v$ $A_1$ $B_1$ $:$ $A_{N-1}$ $B_{N-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
输出 #1
2
输入 #2
5 4 5 1 2 1 3 1 4 1 5
输出 #2
1
输入 #3
2 1 2 1 2
输出 #3
0
输入 #4
9 6 1 1 2 2 3 3 4 4 5 5 6 4 7 7 8 8 9
输出 #4
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$ 次。
注意，每一回合都不能停留在原地。
- $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$ 次。
注意，每一回合都不能停留在原地。