[SHOI2014]概率充电器

• 链接 P4284 [SHOI2014]概率充电器

• 首有个朴素的想法就是设\(f_i\)表示考虑完子树后节点\(i\)通电的概率，然后换根\(dp\)一下。
• 但是这样不好算：因为这样算的是自己本身有电，或者儿子有电的概率。
• 考虑转化一下，\(f_i\)表示考虑完子树后节点\(i\)没电的概率，然后换根\(dp\)一下。
• 这样的好处在于算的是自己本身有电，并且儿子有电的概率。
• 这样就可以直接乘起来了，即
  \[f_i=(1-v_i)*\prod (f_v+(1-f_v)*(1-w_v))\]
• 最后换根一下考虑每个节点作为根节点的概率。

• 复杂度\(O(n)\)

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define R register int
#define db double
using namespace std;
const int N=1000001;
int n,u,v,cnt;db x,f[N],w[N],vl[N],ans;
int hd[N],to[N],nt[N];
void link(R f,R t,db d){nt[++cnt]=hd[f],to[cnt]=t,w[cnt]=d,hd[f]=cnt;}
int gi(){
    R x=0,k=1;char c=getchar();
    while(c!='-'&&(c<'0'||c>'9'))c=getchar();
    if(c=='-')k=-1,c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar(); 
    return x*k;
}
void Dfs1(R i,R fm){
    f[i]=1.00-vl[i];
    for(R k=hd[i];k;k=nt[k])
        if(to[k]!=fm){
            Dfs1(to[k],i);
            f[i]*=(f[to[k]]+(1.00-w[k])*(1.00-f[to[k]]));
        }
}
void Dfs2(R i,R fm){
    ans+=1.00-f[i];
    for(R k=hd[i];k;k=nt[k]){
        if(to[k]==fm)continue;
        db u=f[i],v=f[to[k]];
        f[i]/=(f[to[k]]+(1.00-w[k])*(1.00-f[to[k]]));
        f[to[k]]*=(f[i]+(1.00-w[k])*(1.00-f[i]));
        Dfs2(to[k],i);
        f[i]=u,f[to[k]]=v;
    }
}
int main(){
    n=gi();
    for(R i=1;i<n;++i){
        u=gi(),v=gi(),scanf("%lf",&x);
        x/=100.0,link(u,v,x),link(v,u,x);
    }
    for(R i=1;i<=n;++i)scanf("%lf",&vl[i]),vl[i]/=100.0;
    Dfs1(1,0),Dfs2(1,0),printf("%.6lf\n",ans);
    return 0;
}