LG 4284 [SHOI2014]概率充电器

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转树形 dp 中的$\text{up and down}$还有一点期望设每个点能够通电的概率为$P_i$那么$ans = \sum_{i=1}^n P_i$我们先考虑$up$(只考虑子树))分成两种情况:直接通电 : $q_i$被子节点通电 :$(1-qi) \times P{to}(\text{子节点}) \times e_i.w(\text{连接的边导电的概率})$我们再考虑$down$(考虑子树外))我们可以通过父节点的答案来更新子节点父节点的答案是包括当前子节点的可以把这部分除去然后按照$up……