题意
给出一棵 \(n\) 结点树，从结点 \(x\) 出发，每次从当前点的所有边中选一条走过去，\(Q\) 次询问给定一个点集 \(S\)，随机游走直到经过 \(S\) 中的每一个点至少一次的期望总步数，出发点 \(x\) 默认在开始时已经被经过。
\(n\le 18, Q\le 5000\)
解法
萌新第一次见到这种题，感觉很神。
首先先转化一下询问，设一个点的权值为第一次到达时所用的步数，于是询问就是求 \(S\) 中点权的期望最大值。
期望最大值是不好处理的，转化为期望最小值。
由期望形式的 \(\mathrm{Min-Max}\) 反演有：
于是想到对每个点集 \(T\) 预处理出 \((-1)^{|T|+1}E(min(T))\) 然后使用 \(\mathrm{FWT}\) 计算高维前缀和。
接下来问题变为如何对于每个 \(T\) 快速求解 \(E(min(T))\)，设从 \(i\) 出发第一次到达 \(T\) 中的点的期望步数为 \(f_i\)，那么对于不属于 \(T\) 中的点可以列出转移方程：
我们需要求 \(f_x\) 的值。
转移关系中有环，直接使用高斯消元复杂度显然过于夸张，but 由于树形结构的特殊性，我们可以把 \(f_x\) 视为根，然后使用待定系数法。
考虑对每个 \(i\) 求出满足 \(f_i = k_i f_{fa_i} + b_i\) 的 \(k_i\) 和 \(b_i\)，对于根结点 \(x\) 就有 \(f_x = b_x\)。归纳地考虑，对于叶子结点显然有 \(k = 1, b = 1\)，对于其他结点，其所有叶结点的 \(f\) 均为其一次函数，代入转移方程显然其 \(f\) 值也为其父结点 \(f\) 的一次函数。
具体地推式子：
即
最后只需要求 \(f_x\)，即 \(b_x\)。
萌新从没见过这么神的期望 dp，菜菜。