题意： 给出一棵树，每个节点和边都有一个通电的概率，问发光的节点的期望个数。
吐槽一下： naive。。。先按照感觉，列了能发光概率的式子，后来发现自己分析的漏洞太多了。
题解： 考虑树形动态规划。 很容易知道电流不会跨过当前节点u后再转移到u。 所以，不妨分开子树和子树外来考虑。
然后，很难考虑能发光的概率，就去考虑不能发光的概率。 设计状态f(u)表示子树内不能使u发光的概率，g(u)表示子树外不能使u发光的概率。
转移： 1.
f(u)=(1−p(u))；
2.
f(u)∗=(f(v)+(1−f[v])∗(1−e.p));
3.
T=f[u.fa]/(f[u]+(1−f[u])∗(1−e−>c))∗g[u.fa];
4.
g(u)=T+(1−T)∗(1−e.p)
3.这部分表示除去u的子树对u.fa的影响。
res=∑ni=11−f(i)∗g(i)
转载请注明原文地址: https://ju.6miu.com/read-9154.html
