Description
著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器:
“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!
”
SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。
随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。
你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?
Input
第一行一个整数:n。概率充电器的充电元件个数。充电元件由 1-n 编号。
之后的 n-1 行每行三个整数 a, b, p,描述了一根导线连接了编号为 a 和 b 的
充电元件,通电概率为 p%。
第 n+2 行 n 个整数:qi。表示 i 号元件直接充电的概率为 qi%。
Output
输出一行一个实数,为进入充电状态的元件个数的期望,四舍五入到六位小数
Sample Input
3
1 2 50
1 3 50
50 0 0
Sample Output
1.000000
HINT
对于 100%的数据,n≤500000,0≤p,qi≤100。
树形概率期望dp
充上电的概率不好统计，但是充不上电的概率还是比较容易统计的。用(f[x])表示(x)节点充不上电的概率，那么(now)节点能充上电的期望就是(1-f[now])，定义(ff[x,y])表示边(x,y)不通的概率，
对于每一个节点(now)能够从子树及自己都无法充上电的转移是
由父节点的转移其实本质上是一样的，但是父节点的概率还包含一部分(now)本身的概率，所以要除去，由上一个方程解出就是(f[fa]/(f[now]+(1-f[now])*ff[now]))
表示的是(now)的父亲(fa)因为初了(now)的其他原因充不上电的原因，用(d)来代替的话转移式就变成(f[now]*=d+(1-d)*ff[now])，和第一个转移式是一样的
#include<iostream>
#include<cstdio>
#include<cstring>
#define M 1000021
using namespace std;
int i,m,n,j,k,a[M],ver[M],edge[M],head[M],nex[M],cnt,x,y,z;
double f[M],v[M],ans,ff[M];
inline int gtt()
{
char c=getchar();
int x=0,r=1;
while(c<'0'||c>'9')
{
if(c=='-') r=-1;
c=getchar();
}
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x*r;
}
void add(int x,int y,int z)
{
cnt+=1;
ver[cnt]=y; nex[cnt]=head[x]; head[x]=cnt; edge[cnt]=z;
}
void dfs1(int now,int fa)
{
f[now]=((double)100-a[now])/100;
for(int i=head[now];i;i=nex[i])
{
int t=ver[i];
if(t==fa) continue;
dfs1(t,now);
ff[t]=(double)(100-edge[i])/100;
f[now]*=f[t]+(1-f[t])*ff[t];
}
}
void dfs2(int now,int fa)
{
long double d=f[fa]/(f[now]+(1-f[now])*ff[now]);
if(fa)f[now]*=d+(1-d)*ff[now];
for(int i=head[now];i;i=nex[i])
{
int t=ver[i];
if(t==fa) continue;
else dfs2(t,now);
}
ans+=1-(f[now]);
}
int main()
{
n=gtt();
for(i=1;i<n;++i)
{
x=gtt(); y=gtt(); z=gtt();
add(x,y,z); add(y,x,z);
}
for(i=1;i<=n;++i) a[i]=gtt();
dfs1(1,0);
dfs2(1,0);
printf("%.6lf",ans);
}