CF1912F Fugitive Frenzy

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}$。

下图展示了样例中的树结构。     由 ChatGPT 4.1 翻译