bzoj 3566: [SHOI2014]機率充電器 樹形DP

首先普及一個機率公式 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的機率，明顯出現了循環）具體公式推導見代碼