BZOJ3566:[SHOI2014]概率充电器 树形期望dp

思路:

膜拜的bill125神犇的题解.

(首先将树转化为有根树)

首先求一个节点能够充上电的的概率是很不容易的,我们转化为求一个结点不能充上电的概率,那么分为两部分,分别是这个结点的子节点不能给这个结点充电的概率和这个结点的父亲不能给这个结点充电的概率.

令这两个东西分别为\(f_{i,0},f_{i,1}\).

首先我们dfs一遍求出\(f_{i,0}\).

\[f_{i,0}=(1-q_i)\Pi_{j\in{son(i)}}(f_{son,0}+(1-f_{son,0})*(1-p_{Edge(i,j)}))\]

这一次我们首先考虑的是每个节点对祖先的贡献.

接下来考虑每个节点对子树中节点的贡献.

令\(x\)的父亲为\(pa_x\),令\(t\)表示在除了\(x\)之外的节点的影响下没有被充电的概率,我们有:

\[t=f_{pa_x,0}/(f_{x,0}+(1-f_{x,0})*(1-p_{Edge(x,pa_x)}))*f_{pa_x,1}\]

\[f_{x,1}=t+(1-t)*(1-p_{Edge(x,pa_x)})\]

(注意特判\(t\)不存在的情况)

那么最终节点\(i\)被充电的概率就是\(g_i=1-f_{i,0}*f_{i,1}\),则:

\[ans=\sum_{i=1}^{n}g_i\]

这样就可以\(O(n)\)出解了.

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
 
#define N 500010
 
int head[N],next[N<<1],end[N<<1],pa[N];f2 p[N<<1],pp[N];
inline void addedge(int a,int b,f2 _p){static int q=1;end[q]=b,next[q]=head[a],head[a]=q,p[q++]=_p;}
inline void make(int a,int b,f2 _p){addedge(a,b,_p),addedge(b,a,_p);}
 
f2 f[N][2];
void dfs1(int x,int fa){
    for(int j=head[x];j;j=next[j]){
        if(end[j]!=fa){
            pp[end[j]]=p[j],pa[end[j]]=x,dfs1(end[j],x);
            f[x][0]*=f[end[j]][0]+(1-f[end[j]][0])*(1-pp[end[j]]);
        }
    }
}
void dfs2(int x,int fa){
    f2 t,_p;
    for(int j=head[x];j;j=next[j]){
        if(end[j]!=fa){
            t=f[end[j]][0]+(1-f[end[j]][0])*(1-pp[end[j]]);
            _p=t<1e-6?0:f[x][1]*f[x][0]/t;
            f[end[j]][1]=_p+(1-_p)*(1-pp[end[j]]);
            dfs2(end[j],x);
        }
    }
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
 
    int n;cin>>n;
    register int i,j;int a,b,x;for(i=1;i<n;++i)scanf("%d%d%d",&a,&b,&x),make(a,b,x/100.0);
 
    for(i=1;i<=n;++i)scanf("%d",&x),f[i][0]=1-x/100.0;
    dfs1(1,-1),f[1][1]=1,dfs2(1,-1);
    f2 res=0;for(i=1;i<=n;++i)res+=1-f[i][0]*f[i][1];
    printf("%.6lf",res);
    return 0;
}