概率 dp, 树形 dp
如果求出每个点被通电的概率 t,
那么期望答案就是 t1×1+t2×1+t3*1+...+tn×1
现在问题就是要去求每个点被通电的概率
因为是一颗树, 所以每个点是否通电只由三个因素决定:
自己给自己通电; 儿子给自己通电; 父亲给自己通电
这里采取求反面的方法:
对于每个点 u,
1. 求出 u 所在的子树不能给 u 点通电的概率 f[u]
2. 求出 u 的父亲不能给 u 点通电的概率 g[u]
那么最终, 每个点可以被通电的概率就是 1-f[u]*g[u].
对于 f[u]的求法:
dfs 这颗树, 用儿子 v 去更新父亲节点 u:
$$f[u]=(1-q[u])\times \prod_{u->v:p(边的概率为 p)}(f[v]+(1-f[v])*(1-p))$$
对于 g[u]的求法:
同样的 dfs 这颗树, 用父亲 u 去更新儿子节点 v
先求出除了 v 之外, 其他的点使得 u 通电的概率: t=f[u]*g[u]/(f[v]+(1-f[v])*(1-p));
(就是除掉儿子对父亲的贡献, 注意 (f[v]+(1-f[v])*(1-p)) 等于 0 的情况)
然后 $$g[v]=t+(1-t)\times (1-p)$$
来源: http://www.bubuko.com/infodetail-2523290.html