Gauss's blog

Gauss's blog

I’d go back to December turn around and make it alright.

题解 P4284「SHOI 2014」概率充电器

posted on 2021-07-19 17:21:18 | under 树形dp |

Description

「SHOI 2014」概率充电器

Analysis

由期望的线性性,易知答案为所有充电元件进入充电状态的概率之和。

设点 $u$ 个点直接充电的概率为 $\mathbb P(u)$,边 $(u,v)$ 导电的概率为 $\mathbb P(u,v)$。

选定某个点为根,对这棵树进行树形 dp,设 $f_u$ 为只考虑 $u$ 的子树内的点和边,点 $u$ 进入充电状态的概率。

可得状态转移方程$$f_u=(1-\mathbb P(u))\prod_{u\text{ is the father of }v}(1-\mathbb P(u,v)+\mathbb P(u,v)f_v)$$ 接下来换根 dp 即可得到每个点进入充电状态的概率,统计答案即可。

Code

代码