题目链接

题解

设\(f[i][S]\)表示从\(i\)节点出发，走完\(S\)集合中的点的期望步数

记\(de[i]\)为\(i\)的度数，\(E\)为边集，我们很容易写出状态转移方程

①若\(i \notin S\)

\[f[i][S] = \frac{1}{de[i]}\sum\limits_{(i,j) \in E}(f[j][S] + 1)\]

②若\(i \in S\)

除非\(\{i\} = S\)，\(f[i][S] = 0\)

否则

\[f[i][S] = \frac{1}{de[i]}\sum\limits_{(i,j) \in E}(f[j][S - \{i\}] + 1)\]

容易发现转移到的集合\(S'\)要么是\(S\)，要么是更小的集合\(S - \{i\}\)

状态数是\(O(n2^{n})\)，如果我们按\(S\)逐一从小计算，计算当前\(S\)时，转移到的\(S - \{i\}\)则可以直接算出

而如果转移到当前的\(S\)，这个方程则有了后效性

直接高斯消元是\(O(n^{3}2^{n})\)的，我们考虑如hdu Maze那题一样解出式子

在集合\(S\)意义下【为了方便我们就省去S这维】，记\(fa[i]\)为\(i\)的父节点，我们不妨设

\[f[i] = A_if[fa[i]] + B_i\]

①若\(i \notin S\)

如果\(i\)为叶节点，那么\(A_i = B_i = 1\)

否则有

\[ \begin{aligned} f[i] &= \frac{1}{de[i]}\sum\limits_{(i,j) \in E}(f[j][S] + 1) \\ &= \frac{1}{d[i]}f[fa[i]] + \frac{1}{de[i]}\sum_{i = fa[j]}(A_jf[i] + B_j + 1) \\ &= \frac{1}{d[i] - \sum_{i = fa[j]}A_j}f[fa[i]] + \frac{\sum_{i = fa[j]}(B_j + 1) + 1}{d[i] - \sum_{i = fa[j]}A_j} \end{aligned} \]

所以

\[ \left\{ \begin{aligned} A_i &= \frac{1}{d[i] - \sum_{i = fa[j]}A_j} \\ B_i &= \frac{\sum_{i = fa[j]}(B_j + 1) + 1}{d[u] - \sum_{i = fa[j]}A_j} \end{aligned} \right. \]

可以由儿子递推

②若\(i \in S\)

除非\(\{i\} = S\)，此时\(A_i = B_i = 0\)

否则\(A_i = 0\)，\(B_i = \frac{1}{de[i]}\sum\limits_{(i,j) \in E}(f[j][S - \{i\}] + 1)\)

计算出所有\(A_i\)和\(B_i\)后回代可得到\(f[i][S]\)

至此可以\(O(n2^n)\)预处理所有\(f[i][S]\)

然后做到\(O(1)\)回答询问

根本不需要什么minmax容斥，\(O(3^n)\)子集枚举

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include