← 返回题目
题库练习 [ABC148F] Playing Tag on Tree
← 上一题 下一题 →

A7542 | [ABC148F] Playing Tag on Tree

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

有一棵包含 $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
输出 #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
C++ 编辑器
输入
输出