#2482. 「CEOI2017」Mousetrap

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

有一个有 n 个房间和 n-1 条走廊的迷宫,保证任意两个房间可以通过走廊互相到达,换句话说,这个迷宫的结构是一棵树。
一个老鼠被放进了迷宫,迷宫的管理者决定和老鼠做个游戏。
一开始,有一个房间被放置了陷阱,老鼠出现在另一个房间。老鼠可以通过走廊到达别的房间,但是会弄脏它经过的走廊。老鼠不愿意通过脏的走廊。
每个时刻,管理者可以进行一次操作:堵住一条走廊使得老鼠不能通过,或者擦干净一条走廊使得老鼠可以通过。然后老鼠会通过一条干净的并且没被堵住的走廊到达另一个房间。只有在没有这样的走廊的情况下,老鼠才不会动。一开始所有走廊都是干净的。管理者不能疏通已经被堵住的走廊。
现在管理者希望通过尽量少的操作将老鼠赶到有陷阱的房间,而老鼠则希望管理者的操作数尽量多。请计算双方都采取最优策略的情况下管理者需要的操作数量。
注意:管理者可以选择在一些时刻不操作。

输入格式

第一行三个空格隔开的正整数数 n,t,m 。分别代表房间的个数,陷阱房的编号和老鼠起始房间的编号。
接下来 n-1 行,每行两个空格隔开的整数 a_i,b_i ,表示有一条走廊连接编号为 a_i b_i 的房间。

输出格式

输出一行包含一个整数,表示双方都采取最优策略的情况下,管理者需要的操作数量。

样例

样例输入

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

样例输出

4

样例解释

  • 管理者先堵住房间 4 7 之间的走廊。
  • 老鼠走到房间 6 。房间 4 6 之间的走廊现在是脏的。
  • 管理者堵住房间 6 8 之间的走廊。
  • 老鼠不能动。
  • 管理者清理房间 4 6 之间的走廊,房间 4 6 之间的走廊现在是干净的。
  • 老鼠走到房间 4 ,房间 4 6 之间的走廊现在是脏的。
  • 管理者堵住房间 2 3 之间的走廊。
  • 老鼠走到房间 2 ,房间 2 4 之间的走廊现在是脏的。
  • 管理者不进行操作。
  • 老鼠走到房间 1

这个过程中管理者总共进行了 4 次操作。

数据范围与提示

  • 子任务 1( 20\% ): 1\le n\le 10
  • 子任务 2( 25\% ): 1\le n\le 10^6 ,保证老鼠的起始位置和陷阱房相邻;
  • 子任务 3( 20\% ): 1\le n\le 1000
  • 子任务 4( 35\% ): 1\le n\le 10^6