P5643 [PKUWC2018]随机游走

洛谷：P5643 [PKUWC2018]随机游走

Solution

对点集 $S$，记 $\max(S)$ 表示将 $S$ 中所有点都遍历过的步数，$\min(S)$ 表示第一次遍历到 $S$ 中任意一个点所经历的步数。运用 min-max 容斥，有：

\[E[\max(S)] = \sum\limits_{T \subseteq S, T \neq \emptyset}(-1)^{|T| + 1}E[\min(T)] \]

问题转化为求 $S$ 的每个子集 $T$ 的 $E[\min(T)]$。

设 $f_{S, u}$ 表示从 $u$ 出发，第一次遍历到 $S$ 中的点的期望步数。记 $d_{u}$ 表示 $u$ 的度数，$fa_{u}$ 表示 $u$ 的父亲，$son(u)$ 表示 $u$ 的儿子集合。

若 $u \in S$，则 $f_{S, u} = 0$。否则：

\[f_{S, u} = \frac{1}{d_{u}}\left( f_{S, fa_u} + 1 + \sum\limits_{v \in son(u)}(f_{S, v} + 1) \right) \]

方便转移，我们希望 $f_{S, u}$ 只由 $f_{S, fa_u}$ 以及一些容易预处理的信息决定。

设 $f_{S, u} = A_{u}f_{S, fa_{u}} + B_{u}$。（套路相关：洛谷：P3251 [JLOI2012]时间流逝）

记 $\sigma_{u}(A) = \sum\limits_{v \in son(u)}A_v, \sigma_{u}(B) = \sum\limits_{v \in son(u)}B_v, \sigma_{u}(1) = \sum\limits_{v \in son(u)}1$。

\[\begin{aligned} f_{S, u} &= \frac{1}{d_{u}}\left( f_{S, fa_u} + 1 + \sum\limits_{v \in son(u)}(f_{S, v} + 1) \right) \\ d_{u}f_{S, u} &= f_{S, fa_u} + 1 + \sum\limits_{v \in son(u)}(A_vf_{S, u} + B_v + 1) \\ d_{u}f_{S, u} &= f_{S, fa_u} + 1 + \sigma_{u}(A)f_{S, u} + \sigma_{u}(B) + \sigma_{u}(1) \\ ( d_u - \sigma_{u}(A))f_{S, u} &= f_{S, fa_u} + \sigma_{u}(B) + \sigma_{u}(1) + 1 \\ f_{S, u} &= \frac{1}{d_u - \sigma_{u}(A)}f_{S, fa_u} + \frac{\sigma_{u}(B) + d_{u}}{d_u - \sigma_{u}(A)} \end{aligned} \]

故 $A_u = \frac{1}{d_u - \sigma_{u}(A)}, B_u = \frac{\sigma_{u}(B) + d_{u}}{d_u - \sigma_{u}(A)} $。

注意：对于 $u \in S$，不能简单地只把 $f_{S, u}$ 赋成 $0$，因为 $f_{S, u}$ 会由 $A_u$ 和 $B_u$ 决定，右式不为 $0$ 时，系数的转移就会出问题。

解决办法就是把 $A_u, B_u$ 赋成 $0$，这样等式一定成立。

对每个子集 $S$ 求一遍 $f$ 的过程是 $O(n2^n)$ 的，这样 $E[\min(S)] = f_{S, root} = B_{root}$（$root$ 为题目给定的初始点）的问题就解决了。

把 $f_{S, fa_{root}}$ 赋成 $0$ 的实际含义：观察最初的式子 $f_{S, u} = \frac{1}{d_{u}}\left( f_{S, fa_u} + 1 + \sum\limits_{v \in son(u)}(f_{S, v} + 1) \right)$，由于 $root$ 没有父节点，因此 $f_{S, fa_u} + 1$ 的那一项就被省了，但由于最开始 $root$ 自己就已经算了一步，因此其实只有 $f_{S, fa_{root}}$ 被省去，所以最终反映出来一次函数中把 $f_{S, fa_{root}}$ 赋为了 $0$。

最后所求为 $B_{root}$，因此实际实现时用不到 $f$ 数组。

当某个点 $u\in S$ 时，可直接返回，不用遍历子树。

不用枚举 $S = \emptyset$。