Playing Tag on Tree

题目描述

我们有一棵有 $N$ 个顶点的树。第 $i$ 条边双向连接顶点 $A_i$ 和 $B_i$。 Takahashi 站在顶点 $u$，Aoki 站在顶点 $v$。 现在，他们将按如下规则玩躲猫猫（tag）游戏：

$1$. 如果 Takahashi 和 Aoki 站在同一顶点，游戏结束。否则，Takahashi 移动到一个由他选择且与他当前顶点相邻的顶点。

$2$. 如果 Takahashi 和 Aoki 站在同一顶点，游戏结束。否则，Aoki 移动到一个由他选择且与他当前顶点相邻的顶点。

$3$. 回到步骤 $1$。

Takahashi 进行他的移动以使游戏尽可能晚结束，而 Aoki 进行他的移动以使游戏尽可能早结束。 在双方都知道对方的位置和策略的情况下，求游戏结束前 Aoki 将进行的移动次数。 可以证明游戏一定会结束。

输入格式

输入按以下格式从标准输入给出： $N$ $u$ $v$ $A_1$ $B_1$ : $A_{N-1}$ $B_{N-1}$

输出格式

输出游戏结束前 Aoki 将进行的移动次数。

5 4 1
1 2
2 3
3 4
3 5

2

5 4 5
1 2
1 3
1 4
1 5

1

2 1 2
1 2

0

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$ 给定的图是树。如果双方都采用最优策略，游戏将如下进行：

Takahashi 移动到顶点 $3$。 Aoki 移动到顶点 $2$。 Takahashi 移动到顶点 $5$。 Aoki 移动到顶点 $3$。 Takahashi 移动到顶点 $3$。

在这里，Aoki 进行了两次移动。 注意，在每次移动中，不能停留在当前顶点。

标签: AtCoder|abc148F

来源

AtCoder|abc148F