自动搬运

查看原文

来自洛谷，原作者为

	tzl_Dedicatus545 忙碌着 无为着 继续

搬运于2025-08-24 23:15:34，当前版本为作者最后更新于2025-06-28 21:39:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先的观察是 A 和 B 都只会往叶子处走。然后假如 B 决定躲在 $x$ 处，A 能追到 B 当且仅当 A 在一开始就决定往 $x$ 走。

此外，策略一定形如『在 $u$ 点以 $p_{u,v}$ 的概率走到 $v$ 』状物，否则如果存在确定策略的话 B 直接对着叉 A 就完蛋了。

然后考虑列一下方程，大概就是（$p$ 是 A 的概率，$q$ 是 B 的概率）：

$$f_u=\sum_{v\text{ is a leaf},v\neq u}p_{u,v}(d_{u,v}+f_v(1-q_{u,v})) $$

根据纳什均衡，我们对于任意固定的 $u$，有：

$$f_{v}p_{u,v}=A\\ d_{u,v}+f_{v}(1-q_{u,v})=B$$

为定值。你也可以理解为：如果上述式子不全相等，那么另一方一定可以找到最大/最小的那个让答案变劣，所以必定全部相等。

经过一些 dirty work 你可以推导出

$$f_u=\dfrac{|L|-1-[u\in L]+\sum_{v\neq u}\frac{d_{u,v}}{f_v}}{\sum_{v\neq u}\frac{1}{f_v}} $$

带回去迭代 $T=10^5$ 次精度就够了。