1944. 铁憨憨骑士团的反恐演练

时间限制 1000 ms   内存限制 256 MB

在遥远的憨憨王国,有一个铁憨憨骑士团。作为憨憨王国唯一的骑士团,他们需要负责维护憨憨王国的治安。这天,他们决定针对可能发生的恐怖袭击进行演练。

憨憨王国的城市在沙盒上可以被看做由 $n$ 个城市和 $n-1$ 条双向的道路组成,城市由从 $1$ 到 $n$ 的标号表示。每条道路连接两个不同的城市,通过这些道路,任意两座城市之间都是可以相互到达的。

每次演练将由一个骑士扮演恐怖分子,另一个骑士进行追缉。扮演恐怖分子的骑士的目标是,在尽可能多的城市安放炸弹,以造成最大的威胁;负责追缉的骑士的目标则相反。

演练的过程如下:一开始,进行追缉的骑士 $A$ 和扮演恐怖分子的骑士 $B$ 分别位于两个不同的城市中。演练以回合进行,在每一个回合的开始,如果 $B$ 当前所在的城市没有被安放炸弹,那么 $B$ 就会在当前城市安放一颗炸弹。之后,由 $B$ 先行动,他可以沿着一条道路走向另一个城市,或者呆在原城市不动。然后 $A$ 以同样的规则行动。在任意时刻,如果 $A$ 和 $B$ 处于同一个城市,那么 $A$ 成功追缉到 $B$,演练结束。

现在,铁憨憨骑士团的团长憨中憨正在观摩两位骑士进行演练。两位骑士都是绝顶聪明的,他们总会做出最优的决策。但是,憨中憨并不是绝顶聪明的,于是他找到了你,想让你计算这场演练中最终会有多少个城市被安放炸弹。

输入数据

第一行一个整数 $n\ (2\le n \le 10^5)$,表示城市数量。
接下来一共 $n-1$ 行,每行两个整数 $u,v\ (1\le u,v\le n,\ u\neq v)$,表示第 $i$ 条道路连接的两个城市。
接下来一行两个整数 $A,B\ (1\le A,B \le n,\ A\neq B)$,分别表示负责追缉的骑士和扮演恐怖分子的骑士一开始所在的城市。

输出数据

一行一个整数 $ans$,表示最终会有几个城市被安放炸弹。

样例输入

复制
3
1 2
2 3
1 3 \n
 · \n
 · \n
 · \n

样例输出

复制
1 \n

样例说明

一开始,扮演恐怖分子的骑士在 $3$ 号城市安放炸弹,之后走到 $2$ 号城市。然后,负责追缉的骑士走到 $2$ 号城市,抓住恐怖分子,演练结束。

提交

请先 登录

© 2024 FAQs Contact About