\(Description:\)

一棵树，每个点q[i]的概率直接充电，每条边p[i]的概率导电，电可以沿边传递使其他点间接充电。求进入充电状态的点期望个数。

\(Sample\) \(Iuput:\)

3

1 2 50

1 3 50

50 0 0

\(Sample\) \(Input:\)

5

1 2 90

1 3 80

1 4 70

1 5 60

100 10 20 30 40

\(Solution:\)

考虑树形dp，首先我们需要明白，其实我们要求的期望就是概率之和，那么我们只要求出每个点的概率，那么怎么求每个点的概率捏？

yzc提供了一种神奇的办法，考虑对于每个点，先求出每个点的子树的概率和 \(f[u]\)

那么对于一个点 \(u\)，就只要让 \(u\) 的所有儿子到他的概率取个并集，

概率并的求法：

\(P(A \cup B)=P(A)+P(B)-P(A)*P(B)\)

第一遍 \(dfs\) 求出所有的 \(f\)，但这样只是求出了当前这个点的子树给他充电的概率，还没有求父亲给他充电的概率。

那么再纪录一个 \(g\)，数组记录当前的总概率，然后考虑 \(g\) 的转移：

那么我们考虑已经求出了他父亲的 \(g[fa]\) 要求 \(g[v]\)

那么就只要把 当前的点的子树对 \(g[fa]\) 的贡献给除掉就可以了。

求概率补集：

\(P(A)=\frac{P(A \cup B)-P(B)}{1-P(B)}\)\((注意特判1-P(B)==0)\)

那么就可以愉快的用两次 \(dfs\) 求出答案。

#include
    
     using namespace std;typedef double DD;int n,En;DD ans;const int N=5e5+5;inline DD unit(DD a,DD b){    return a+b-a*b;}inline DD split(DD a,DD b){    if(fabs(1.0-b)==0) return 0;    return (a-b)/(1.0-b);}DD f[N],g[N],p[N];int head[N];struct edge{    int next,to;    DD dis;}E[N<<1];inline void add(int from,int to,DD dis){    E[++En].next=head[from];    E[En].to=to;    E[En].dis=dis;    head[from]=En;}inline void dfs1(int u,int fa){    f[u]=p[u];    for(int i=head[u];i;i=E[i].next){        int v=E[i].to;        if(v==fa) continue;        dfs1(v,u);        f[u]=unit(f[u],f[v]*E[i].dis);    }}inline void dfs2(int u,int fa){    for(int i=head[u];i;i=E[i].next){        int v=E[i].to;        if(v==fa) continue;        g[v]=unit(f[v],split(g[u],f[v]*E[i].dis)*E[i].dis);        dfs2(v,u);    }}int main(){    scanf("%d",&n);    for(int i=1;i<=n-1;++i){        int u=0,v=0,w=0;        scanf("%d%d%d",&u,&v,&w);        add(u,v,(DD)w/100);        add(v,u,(DD)w/100);    }    for(int i=1;i<=n;++i){        int x=0;        scanf("%d",&x);        p[i]=(DD)x/100;    }    dfs1(1,1);    g[1]=f[1];    dfs2(1,1);    for(int i=1;i<=n;++i) ans+=g[i];    printf("%.6lf\n",ans);    return 0;}