首先普及一个概率公式 P(A+B)=P(A)+P(B)-P(AB)
题意:一些充电元件和导线构成一棵树,充电元件是否能充电有2种情况,
1、它自己有qi%的概率充电
2、与它相邻的元件通过导线给它充电(导线有p%的概率导通)
求最终充了电的元件的期望
题解:首先可以将元件能否充电分成3种情况考虑,
1、它自己给自己充好了电
2、它的儿子方向给它传送了电
3、它的父亲方向给它传送了电。
对于1,题目已经给出可以直接赋值,
对于2,可以通过一次树的深度遍历求得。pson[now]=pson[now] + pson[to]*edge_p - pson[now]*pson[to]*edge_p
对于3,麻烦一点,因为2中我们已经求得当前点(now)的儿子们给当前点的贡献,现在要求当前点给它的某个儿子(to)的贡献,这里要计算的话,就必须要排除之前to->now的,(想想若2中计算了to->now的概率,现在又要计算now->to的概率,明显出现了循环)具体公式推导见代码