换根DP好题
我先来讲一个错误的思路
设\(f[i]\)表示只考虑\(i\)及其子树的时候，\(i\)通电的概率
有
\[f[i]=q_i+(1-q_i)(1- \prod_{v} (f[v](1-p_{(v,i)})+1-f[v])) \]化简为
\[f[i]=q_i+(1-q_i)(1- \prod_{v} (1-f[v]p_{(v,i)})) \]其中\(v\)是\(i\)的儿子，\(p_{(v,i)}\)表示这条边的概率
解释一下：分两种情况，
若\(i\)自己亮了，那么样本空间剩下的边和点随便是什么状态都可以
若\(i\)自己没亮，那么必须要至少有一个儿子亮了且这条边一定能够通电。我们考虑这种情况的反面，对任意一个儿子\(v\)，它不亮的概率是\(1-f[v]\)，亮了但是边不通电的概率是\(f[v](1-p_{(v,i)})\)，两者加起来即可。再将上述结果累乘就是反面的概率
我们再设\(g[i]\)表示\(i\)的父亲\(fa\)在不考虑\(i\)及其子树的情况下通电的情况，\(dfa\)表示\(fa\)的父亲
有
\[g[i]=q_{fa}+(1-q_{fa})(1-(1-g[fa]p_{(fa,dfa)})\prod_{v≠i}(1-f[v]p_{(fa,v)})) \]，其中\(v\)是\(fa\)的儿子
情况讨论是类似的，想一下这个公式怎么来的
然后设\(ans[i]\)表示\(i\)通电的概率，有
\[ans[i]=f[i]+(1-f[i])p_{(i,fa)}g[i] \]，其中\(fa\)是\(i\)的父亲
解释一下：最终\(i\)通电要么是由于子树的原因，要么子树没有能够供电，然后父亲来供电
这个解法是错的，错在哪里？错就错在
标签：概率,充电器,fa,子树,ans,通电,prod From： https://www.cnblogs.com/dingxingdi/p/18071033