首先根据那啥啥期望的线性性,被充电原件的期望个数等于所有原件被充电的概率之和,于是我们考虑如何计算每一个原件被充电的概率
首先自己被充电和被导电两个概率是互相独立的,计算还得容斥很麻烦,于是我们考虑转为计算每个原件不会被导电的概率。一个原件不导电就是自己没电,别的节点也不会给它电。而别的节点的情况也分为两类,一是自己就没电,二是自己有电但边不导电而这两个事件是互相独立的
我们先用树形dp计算出一个点不会被子树内的点导电的概率是多少,设\(dp_i\)表示点\(i\)不导电的概率,\(P_i\)表示点\(i\)导电概率,\(val_i\)表示这条边导电的概率,则\(dp_u=(1-P_u)\prod dp_v+(1-dp_v)(1-val_i)\)
然后考虑\(i\)不会被子树外的点充上电的概率,设\(fa_i\)为点\(i\)不会被父亲充电的概率,那么点\(i\)不会被充电的概率就是\(fa_i*dp_i\),即父亲和子树都不会使它充上电。
然后考虑怎么转移,比方说\(u\)是\(v\)的父亲,那么\(v\)不会被\(u\)充电的情况就是\(u\)没电或有电但边不导电。如何计算不考虑\(v\)的子树时\(u\)不导电的概率?因为转移是通过乘法原理转移的,所以只要把\(v\)对\(u\)的贡献除去即可,也就是说只要用\(u\)不会被充电的总概率除以\(v\)不会使\(u\)充上电的概率即可
于是只要两边dfs,一遍求\(dp\),一遍求\(fa\)就可以了
如果有没讲清楚的地方可以看代码,代码应该还蛮好理解的
//minamoto#includeusing namespace std;typedef double db;const int N=5e5+5;int head[N],Next[N<<1],ver[N<<1],tot;db edge[N<<1];inline void add(int u,int v,db e){ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;}db son[N],fa[N],st[N],res,p;int n;void dfs1(int u,int fat){ son[u]=1.0-st[u]; for(int i=head[u];i;i=Next[i]){ int v=ver[i];if(v==fat)continue;dfs1(v,u); son[u]*=son[v]+(1.0-son[v])*(1.0-edge[i]); }}void dfs2(int u,int fat){ for(int i=head[u];i;i=Next[i]){ int v=ver[i];if(v==fat)continue; p=fa[u]*son[u]/(son[v]+(1.0-son[v])*(1.0-edge[i])); fa[v]=p+(1.0-p)*(1.0-edge[i]);dfs2(v,u); }}int main(){// freopen("testdata.in","r",stdin); scanf("%d",&n); for(int i=1,u,v,e;i