首先至少都经过一次不是很好搞，我们希望转化为经过其中某一个点的最少步数期望。
不难发现两者的关系便是广义 min/max，考虑 min-max 容斥在期望意义下的可行性，有：
\[E(max) = \sum_{T \subseteq S} (-1)^{|T| + 1} E(min)
\]
其中 max 便代表第一次经过 \(S\) 中点的最大步数期望，min 便代表经过 \(S\) 中某一点的最小步数期望。
为什么要转化成 \(min\)，因为接下来就变成了一个经典的树形 DP，设 \(f_i\) 为 \(i\) 点开头的答案，这种期望题我们通常倒着做，则有：
\[f_x = \frac{1}{in_x} \sum_{x \to v} f_v + 1
\]
你直接高斯消元也行，但是有基于树形随机游走高斯消元经典 \(O(n)\) 做法，具体来说就是写出 \(f_x\) 关于 \(f_{fa}\) 的表达式，倒着从叶子向上递推即可。
最后一步我们不能 \(O(3^{18})\) 求，考虑依次对于每一维求取前缀和，就是高维前缀和，就做完了。