Luogu

BZOJ

分析

设$f[i]$表示只考虑$i$的子树，$i$没有电的概率，$g[i]$表示$i$的父亲不向$i$供电的概率。

答案为$\sum\limits_{i=1}^n(1-f[i]\times g[i])$。

然后就有：（$a_i$是$i$直接通电的概率，$w$是边导电的概率）

$\large f[i]=a_i\times\prod\limits_{v\in Son_i}\Big[f[v]+(1-f[v])\times(1-w)\Big]$

设一个$\large h[i]=f[i]+(1-f[i])\times(1-w)$

然后得到$\large g[i]=f[fa]\times g[fa]/h[i]$。

求$g$的时候可能会有$h[i]=0$这种情况，要特判一下。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=500000+10;
const double EPS=1e-8;

struct Edge { int v,nxt; double w; };
Edge e[MAXN<<1];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v,double w) {
    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}

int n;
double a[MAXN];
double f[MAXN],g[MAXN],h[MAXN];

inline void dfs1(int u,int fa) {
    f[u]=a[u];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; double w=e[i].w;
        if (v==fa) continue;
        dfs1(v,u);
        h[v]=f[v]+(1-f[v])*(1-w);
        f[u]*=h[v];
    }
}

inline void dfs2(int u,int fa) {
    double sum=a[u]; int z=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        if (h[v]>EPS) sum*=h[v];
        else ++z;
    }
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; double w=e[i].w,tmp;
        if (v==fa) continue;
        if (h[v]>EPS) tmp=z?0:sum/h[v]*g[u];
        else tmp=z>1?0:sum*g[u];
        g[v]=tmp+(1-tmp)*(1-w);
        dfs2(v,u);
    }
}        

int main() {
    n=read();
    for (re int i=1,u,v,w;i<n;++i) {
        u=read(),v=read(),w=read();
        addEdge(u,v,w*0.01); addEdge(v,u,w*0.01);
    }
    for (re int i=1;i<=n;++i) a[i]=1.0-read()*0.01;
    dfs1(1,0); g[1]=1; dfs2(1,0);
    double ans=0;
    for (re int i=1;i<=n;++i) ans+=1.0-f[i]*g[i];
    printf("%.6lf\n",ans);
    return 0;
}