题解：P4321 随机漫游

考虑每个点被走到的时刻 $t_i$，答案为 $E(\max t_i)$。一手 min-max 容斥，转换为 $E(\min\limits_{i\in U}t_i)$。令 $f_{u,s}$ 代表，从点 $u$ 开始随机游走，走到 $s$ 中任何一个点的期望时间。答案就是 $\sum\limits_{U\subset S}-1^{|U|+1}f_{x,U}$，可以将 $f_{x,U}$ 乘上系数然后放进 sosdp 里跑出子集和，这样求答案就是 $O(1)$ 的了。考虑如何求 $f_{u,s}$，首先显然有对于 $u\in s,f_{u,s}=0$，另一个朴素的转移是 $f_{u,s}=1+\sum\limits_{(u,v)\in E}\frac{f_{v,s}}{\text{deg}_u}$。可以对于每个 $s$ 跑一遍高斯消元，总复杂度为 $O(2^nn^3+qn)$，可以通过通过本题。

submission：https://www.luogu.com.cn/record/232972449