显然这是一棵树。
设节点(i)和(j)之间的边为((i,j)),边((i,j))导电的概率为(q_{i,j}),第(i)个点自身有电的概率为(p_i)
考虑树形dp。
显然答案等于所有节点有电的概率之和。
考虑一个节点什么时候会被充电:
1.它自己有电;
2.它的孩子里有节点有电,并且这个孩子和这个节点之间的导线是导电的;
3.它的父亲有电,并且这个节点和父亲之间的导线导电。
本着树形dp的思路,先不考虑父亲对儿子的影响,即先不考虑3。
我们设(dp_i)表示第(i)个节点在考虑自身及其子树以后,有电的概率。
然后我们发现这样一来很难得知某一个儿子对父亲的概率贡献。
于是我们记(dp_i)表示第(i)个节点在考虑自身及其子树以后,没有电的概率。
我们设(i)的孩子为(s_1,s_2,s_3,...,s_m)。
则有(dp_i=(1-p_i)Pi_{j=1}^m(dp_{s_j}+(1-dp_{s_j}) imes (1-q_{i,s_j}))
解释:
我们知道一些时间同时发生的概率为这些时间独立概率的乘积。
要让(i)没电,就要求它自己没电,它的儿子也全部没电,或者有电的孩子和(i)之间的导线不导电。
(i)本身没电的概率是((1-p_i));
孩子(s_j)没电的概率是(dp_{s_j}),孩子(s_j)有电,且((i,s_j))不导电的概率是((1-dp_{s_j}) imes(1-q_{i,s_j})),那么孩子(s_j)到(i)这一段没电的概率就是两者的和,即(dp_{s_j}+(1-dp_{s_j}) imes(1-q_{i,s_j}))。
所以上面的式子就是把这些东西乘起来了。
发现每个孩子对于答案的贡献是独立的(这就是设(dp_i)的意义的理由)。
于是点(i)去除孩子(s_j)以后,剩下部分没电的概率就是(frac{dp_i}{dp_{s_j}+(1-dp_{s_j}) imes(1-q_{i,s_j})})。
有什么用?
一会儿就知道了。
之后我们来考虑点(i)的父亲(f_i)对(i)的影响。
我们记(DP_i)为点(i)的父亲没有电传到(i)的概率。
我们记
(T=DP_{f_i} imes frac{dp_{f_i}}{dp_i+(1-dp_i) imes q_{f_i,i}})
也就是(f_i)不算(i)这棵子树,剩下的部分使得(f_i)没电的概率。
那么有
(DP_i=T+(1-T) imes(1-q_{f_i,i}))
解释:
前一个部分意义上面已经提过;
((1-T))即(f_i)不算(i)这棵子树,剩下的部分使得(f_i)有电的概率,((1-q_{f_i,i}))即边((f_i,i))不导电的概率,那么整个就是(f_i)有电而((f_i,i))没电的概率。
两个部分都算完了。
于是看看答案等于什么。
点(i)没电的总概率就是(dp_i imes DP_i);
那么点(i)有电的概率就是(1-dp_i imes DP_i);
答案就是(sum_{i=1}^n(1-dp_i imes DP_i))。
code:
#include<bits/stdc++.h>
#define Merge(x,y,val) (dps[x]*=(g[y]=dps[y]+(1-dps[y])*(1-val)))
using namespace std;
struct edge{
int t,nxt;
double v;
}e[1000010];
int n,u,v,w,cnt,be[500010],vis[500010],f[500010];
double p[500010],g[500010],fv[500010],dps[500010],dpf[500010],ans;
void add(int x,int y,int val){
e[++cnt].t=y,e[cnt].v=val*0.01,e[cnt].nxt=be[x],be[x]=cnt;
}
void dfs1(int x){
vis[x]=1,dps[x]=1-p[x];
for(int i=be[x];i;i=e[i].nxt)!vis[e[i].t]?dfs1(e[i].t),Merge(x,e[i].t,e[i].v),0:(f[x]=e[i].t,fv[x]=e[i].v);
}
void dfs2(int x){
dpf[x]=f[x]?(g[x]?dpf[f[x]]*dps[f[x]]/g[x]+(1-dpf[f[x]]*dps[f[x]]/g[x])*(1-fv[x]):0):1;
ans+=1-dps[x]*dpf[x];
for(int i=be[x];i;i=e[i].nxt)e[i].t!=f[x]?dfs2(e[i].t),0:0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;++i)scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
for(int i=1;i<=n;++i)scanf("%lf",&p[i]),p[i]*=0.01;
dfs1(1),dfs2(1);
printf("%.6lf",ans);
return 0;
}