[2019.3.7]BZOJ3566 [SHOI2014]概率充电器(树形dp/概率与期望)
xryjr233
·
·
题解
显然这是一棵树。
设节点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})\times (1-q_{i,s_j})
解释:
我们知道一些时间同时发生的概率为这些时间独立概率的乘积。
要让i没电,就要求它自己没电,它的儿子也全部没电,或者有电的孩子和i之间的导线不导电。
孩子$s_j$没电的概率是$dp_{s_j}$,孩子$s_j$有电,且$(i,s_j)$不导电的概率是$(1-dp_{s_j})\times(1-q_{i,s_j})$,那么孩子$s_j$到$i$这一段没电的概率就是两者的和,即$dp_{s_j}+(1-dp_{s_j})\times(1-q_{i,s_j})$。
所以上面的式子就是把这些东西乘起来了。
发现每个孩子对于答案的贡献是独立的(这就是设$dp_i$的意义的理由)。
于是点$i$去除孩子$s_j$以后,剩下部分没电的概率就是$\frac{dp_i}{dp_{s_j}+(1-dp_{s_j})\times(1-q_{i,s_j})}$。
有什么用?
一会儿就知道了。
之后我们来考虑点$i$的父亲$f_i$对$i$的影响。
我们记$DP_i$为点$i$的父亲**没有**电传到$i$的概率。
我们记
$T=DP_{f_i}\times \frac{dp_{f_i}}{dp_i+(1-dp_i)\times q_{f_i,i}}
也就是f_i不算i这棵子树,剩下的部分使得f_i没电的概率。
那么有
DP_i=T+(1-T)\times(1-q_{f_i,i})
解释:
前一个部分意义上面已经提过;
两个部分都算完了。
于是看看答案等于什么。
点$i$没电的总概率就是$dp_i\times DP_i$;
那么点$i$有电的概率就是$1-dp_i\times DP_i$;
答案就是$\sum_{i=1}^n(1-dp_i\times DP_i)$。
code:
```cpp
#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;
}
```