[SHOI2014]概率充电器 [期望dp]

[SHOI2014] 概率充电器

树形dp(换根)+期望

我开始想了一个类似保安站岗的思路 但好像不太对

一个元件充上电守它自己、它父亲还有儿子的影响 正着想不太容易 所以设\(f_u\)表示\(u\)不能充电的概率

故\(f_u=(1-p_u)*\Pi_v((1-e[i].w)(1-f_v)+f_v)=(1-p_u)*\Pi_v(1-e[i].w+e[i].w*f_v)\) 然后求期望个数 再从父亲传递给孩子

设\(g_u\)表示\(u\)为根时的答案 在传递下去时要除去\(v\)的贡献

\(g_v=f_v*(1-e[i].w)(1-g_u/(1-e[i].w+e[i].w*f_v))\) 最后答案为\(\sum_i(1-g_i)\)

void dfs(int u,int ff){
    f[u]=1.0-a[u];
    for(int i=head[u],v;i;i=e[i].nxt)
    if((v=e[i].v)!=ff)
        dfs(v,u),f[u]*=(1.0-e[i].w+e[i].w*f[v]);
}
void dfs2(int u,int ff){
    if(!ff) g[u]=f[u];
    for(int i=head[u],v;i;i=e[i].nxt)
        if((v=e[i].v)!=ff)
            g[v]=f[v]*(1-e[i].w+e[i].w*(g[u]/(1.0-e[i].w+e[i].w*f[v]))),dfs2(v,u);
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    rd(n);
    for(int i=1,u,v,w;i<n;++i) rd(u),rd(v),rd(w),add(u,v,w*0.01);
    for(int i=1;i<=n;++i) scanf("%lf",&a[i]),a[i]*=0.01;
    dfs(1,0),dfs2(1,0);
    for(int i=1;i<=n;++i) ans+=1.0-g[i];
    printf("%.6f",ans);
    return 0;
}