一道不算太难的概率树形 DP?
此处每个结点贡献都是 \(1\),所以相当于算概率。
设 \(a_i = q_i\),\(val_{u,v}\) 表示 \(u,v\) 连边的通电概率,\(son_i\) 表示 \(i\) 的儿子的集合。
再设 \(f_i\) 表示 \(i\) 不被子树内的结点供电的概率,\(g_i\) 表示 \(i\) 不被祖先供电的概率。
首先有转移 \[f_p = (1 - a_p) \prod\limits_{v \in son_p} (f_v + (1 - f_v)(1 - val_{p,v}))\]
考虑到 \(p\) 本身也属于自己的子树,所以先保证 \(p\) 自己不供电。
然后 \(\forall v \in son_p\),要么自己也不从子树供电,要么自己从子树供电但是边不导电。
易得上式。
接着有 \[\begin{align*} P &= \dfrac {f_p \cdot g_p}{f_v + (1 - f_v)(1 - val_{p,v})} \\ g_v &= P + (1 - P)(1 - val_{p,v}) \\ (v &\in son_p) \end{align*}\]
同样有两种情况,父节点不供电或者父节点供电但是不导电。
那么我们考虑算出 \(P\) 即父节点不供电的概率。
显然它不能从子树中供电也不能从父节点的祖先供电,即 \(f_p \cdot g_p\)。
而且 \(v\) 的贡献要删去。
同时注意根节点的 \(g\) 值为 \(1\)。
统计答案时,即 \(\sum\limits_{i = 1}^n (1 - f_i \cdot g_i)\)。
因为从祖先或是从子树两者都满足它才没电。
代码:
1 |
|