$solution:$
因为每个点的贡献均为 $1$ 所以期望等于每个充电的概率和。
设 $f_u$ 表示 $u$ 号点没有被自身与儿子充电的概率, $g_u$ 表示没有被父亲充电的概率, $V_u$ 表示自身充电的概率, $W_{u,v}$ 表示 $u$ 与 $v$ 连接线充电的概率。
则 $f_u=(1-V_u)\times\sum_{v\in son_u} f_v+(1-f_v)\times (1-W_{u,v})$ 。
设 $P$ 表示此点没有充电的概率。则因为钦定 $v$ 点没电所以 $P=\frac{f_u\times g_u}{ f_v+(1-f_v)\times (1-W_{u,v})}$ 。
$g_u=P+(1-P)\times (1-W_{u,v})$ 。
最后期望即为$\sum_{i=1}^n 1-f_i\times g_i$。
原文：https://www.cnblogs.com/si-rui-yang/p/10847166.html