P3317 [SDOI2014]重建 题解

题面

这题挺有意思的。平常的矩阵树定理求的是

\[\sum_T\prod_{e\in T}w_e \]

这题要求

\[\begin{aligned} \sum_T\prod_{e\in T}p_e\prod_{e\not\in T}(1-p_e) &=\sum_T(\prod_{e\in T}p_e\frac{\prod_{e}(1-p_e)}{\prod_{e\in T}(1-p_e)})\\ &=\prod_e (1-p_e)(\sum_T \prod_{e\in T}\frac{p_e}{1-p_e}) \end{aligned} \]

所以直接设 \(w_e=\frac{p_e}{1-p_e}\) 做即可。由于精度限制不高，为了避免分母为 \(0\) 可以设成 \(eps\)。