【概率 DP】CF1874C Jellyfish and EVA 笔记

由题意，原图是 DAG。

由 link 想法，同一位置的状态的概率不均等而同一位置决策的概率均等，不应该从前往后 DP 而应该从后往前 DP。

设 $f_i$ 表示从 $i$ 出发到达 $n$ 的概率，然后对往后怎么选择犯了难，只想到这条路最终能不能到达 $n$ 而没理解最优选择。

实则从 DP 的角度选择，最优选择就是尽量去 $f_v$ 大的 $v$。

抽象一下发现这个结构和 $u,v$ 是什么无关，只与 $f_v$ 的大小和 $|\mathrm{son}(u)|$ 有关。

设 $g_{i,j}$ 表示度数为 $i$，能够去 $f_v$ 第 $j$ 大的的概率。

显然 $g_{i,1}=\frac{1}{i}$，对于 $g_{i,j}$，可以摧毁两条比 $j$ 优的，也可以摧毁一条比 $j$ 优的一条更劣的，注意只有一人在随机操作。

$$g_{i,j}\leftarrow g_{i-2,j-2}\times \frac{j-2}{i}+g_{i-2,j-1}\times \frac{i-j}{i}$$

时间复杂度 $O(n^2+m\log m)$。