有一个有 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 次操作。