← 返回题目列表

Codeforces · 1912/F

F. 逃亡狂潮

中文机器翻译题面 查看原题

F. 市可以表示为一棵树。一名著名的逃犯藏在其中,今天一名忠实的警察决定不惜一切代价抓住他。警察比逃犯更强,但逃犯却比前者快得多。这就是为什么追求如下进行。此时$$$t = 0$$$,警察出现在编号为$$$s$$$的顶点,而逃犯则在他选择的任何其他顶点生成。之后,他们从警察开始轮流。

  • 在警官移动期间,她选择与她当前所在位置相邻的任何顶点并移动到那里。警察花了一分钟的时间移动。此外,警察可能会决定站着不动,在这种情况下,她会在开始移动的顶点等待一分钟。如果在回合结束时,警察最终与逃亡者位于同一顶点,她会立即抓住他,追逐结束。
  • 逃亡者的举动如下。让他在顶点$$$b$$$,警察在顶点$$$p$$$。然后,逃亡者选择任何顶点 $$$b' \ne p$$$,使得顶点 $$$b$$$ 和 $$$b'$$$ 之间的路径不包含顶点 $$$p$$$ 并立即移动到那里。特别是,他总是可以选择 $$$b' = b$$$ 留在原地。逃亡者的行动不需要时间。

请注意,逃犯一周前设法在警察的徽章上安装了无线电窃听器,因此逃犯每时每刻都知道警察的位置(特别是,他知道数字$$$s$$$)。相反,警察对逃犯的行踪一无所知,只有在抓住他的那一刻才能发现他。

警察的目标是尽快抓获逃犯,逃犯的目标是尽可能晚地被抓获。由于追逐可以被认为是一个信息不完整的游戏,参与者可以使用混合(概率)策略——因此,警察的行动是最小化追逐的预期持续时间,而逃犯的行动是最大化它。

求警察和逃犯最优行动下追捕持续时间的数学期望。可以证明它总是有限的。特别是,在最优策略下,追逐无限期持续的概率为零。

输入

第一行包含一个整数 $$$n$$$ — 树中的顶点数 ($$$2 \le n \le 100$$$)。接下来的 $$$n - 1$$$ 行描述了 F 市:每行都包含一对整数 $$$u_i$$$, $$$v_i$$$ — 边端点的编号 ($$$1 \le u_i, v_i \le n$$$)。这些边保证形成一棵树。

最后一行包含一个整数 $$$s$$$ — 警察最初出现的顶点的编号 ($$$1 \le s \le n$$$)。

输出

打印一个实数——警察和逃犯的最佳策略追捕持续时间的数学期望。如果您的答案的绝对或相对误差不超过$$$10^{-6}$$$,则您的答案将被接受;正式地,如果 $$$p$$$ 是你的答案,$$$j$$$ 是陪审团的答案,则应成立:$$$\frac{|p - j|}{\max\{1, |j|\}} \le 10^{-6}$$$。

示例

输入
复制

2
1 2
2

输出
复制

1

输入
复制

3
1 2
1 3
1

输出
复制

2

输入
复制

4
4 3
4 1
4 2
4

输出
复制

3.66667

输入
复制

7
1 4
4 5
5 2
4 6
6 7
7 3
3

输出
复制

8.3525

注意

示例中的树如下所示。