题目链接
solution首先想对于每个二进制位分别计算。
用\(f[i]\)表示第\(i\)个点走到\(n\)异或和为\(1\)的概率。用\(du[i]\)表示第\(i\)个点的度数，那么就有
\[f[u]=\frac{1}{du[u]}(\sum\limits_{w(u,v)=1}(1-f[v])+\sum\limits_{w(u,v)=0}f[v])\\ \Rightarrow du[u]f[u]=\sum\limits_{w(u,v)=1}1-\sum\limits_{w(u,v)=1}f[v]+\sum\limits_{w(u,v)=0}f[v]\\ \Rightarrow \sum\limits_{w(u,v)=1}1=du[u]f[u]+\sum\limits_{w(u,v)=1}f[v]-\sum\limits_{w(u,v)=0}f[v] \]