主要思路

首先，这道题是概率和期望分开算的，进行 DP 时实质上是对概率进行 DP。考虑拆位，设\(dp_b [u]\)为从\(u \to n\)在第\(b\)位为\(1\)的概率，那么显然：

\[ dp_b[u] = \frac{1}{deg[u]}( \sum_{weight(u, v) !\& b} dp_b[v] \sum_{weight(u, v) \& b} (1 – dp_b[v]) ) \]

其中，\((1 – dp_b[v])\)为\(v\)为\(0\)的概率，最后答案消元完就是\(\sum_{i = 1} ans[i] 2^i\)。