考虑 Min-Max 容斥,$\min(S)$ 表示至少一个从 $s$ 走到至少一个属于集合 $S$ 的点的期望时间。

用 $f(i, S)$ 表示集合 $S$ 下 $i$ 到任意 $u \in S$ 的期望时间,则 $\min(S) = f(s, S)$。

$$
f(i, S) =
\begin{cases}
0 &(i \in S) \\
\frac{\sum_{i \to j} f(j, S)}{d_i} + 1 &(i \notin S)
\end{cases}
$$

可通过高斯消元求出,但复杂度过大不能接受。
考虑把原式化为 $f(i) = k_i \times f(father_i) + b_i$ 的形式,推导过程略。
对于每个查询状压处理 $\max(S)$ 不现实,需要处理出子集卷积即可 AC 。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×