题解：P12437 [NERC2023] Fugitive Frenzy

· · 题解

首先的观察是 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 次精度就够了。