求出所有 \(E_{\min}(S)\) ,然后 FWT 求 \(E_{\max}(S)\)
枚举集合 \(S\),记 \(f_{u}\) 表示从终点 \(u\) 走到 \(S\) 中节点的期望步数。
对于不属于 \(S\) 的点 \(u\) , 有:
\[f_{u}=1+\frac{1}{\deg_u}\left(f_{fa}+\sum_{v}f_{v}\right) \]叶子节点只有 \(f_{fa}\) 的贡献,这提示我们将 \(f_u\) 拆分为 \(f_{fa}\) 的贡献和常数。
当然,根的 \(f\) 值即为常数部分。
\[\begin{cases} f_{u}=A_uf_{fa}+B_u \\ f_{u}=1+\frac{1}{\deg u}f_{fa}+\frac{1}{\deg u}(\sum_{v}A_vf_u+B_v) \end{cases} \\ \Rightarrow \begin{cases} A_u= \frac{1}{\deg u - \sum_{v}A_v}\\ B_u= \frac{\deg u+\sum_{v}B_v}{\deg u-\sum_{v}A_v} \end{cases} \]并且对于叶子有 \(A_u=1,B_u=1\)
直接做可以做到 \(\mathcal O(n2^n)\)
标签:frac,sum,P5643,fa,游走,cases,PKUWC2018,deg From: https://www.cnblogs.com/chihik/p/P5643.html