LINK：概率充电器
大概是一个比较水的题目 不过有一些坑点.
根据期望的线性性 可以直接计算每个元件的期望 累和即为答案.
考虑统计每一个元件的概率的话 那么对其有贡献就是儿子 父亲 以及自己.
自己很容易算 儿子也很容易 父亲的话需要dfs一下父亲那边即可。
不过这样做是n^2。一个容易误解的地方 儿子能传给父亲父亲能传给儿子 这样就带环了Y.
不过 我们单独考虑时 当儿子传给父亲时 儿子一定是亮的 所以这个dp是无环的。
容易想到换根dp.不过需要算出去掉某个儿子之后的概率.
设当前概率为now,以前概率为x 当前儿子贡献的概率为tn 那么显然有 (now=x+(1-x)cdot tn)
化简一下 ((1-tn)x=now-tn)
值得一提的是tn为1的时候右边会除以0 这是不合法的 而我们也没有什么做法可以解决这个问题。
一个小trick 其实可以不用给儿子去传递概率了 因为儿子此时概率为1 不传递也是正确的。
const int MAXN=500010;
int n,len;
int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1];
db ans,e[MAXN<<1],a[MAXN],f[MAXN];
inline void add(int x,int y,int z)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
e[len]=z*1.0/100;
}
inline void dfs(int x,int fa)
{
f[x]=a[x];
go(x)
{
if(tn!=fa)
{
dfs(tn,x);
f[x]+=(1-f[x])*f[tn]*e[i];
}
}
}
inline void dp(int x,int fa,db v)
{
ans+=f[x]+(1-f[x])*v;
go(x)
{
if(tn!=fa)
{
if(fabs(f[tn]*e[i]-1)<=EPS)dp(tn,x,0);
else
{
db ww=(f[x]-f[tn]*e[i])/(1-f[tn]*e[i]);
dp(tn,x,((1-ww)*v+ww)*e[i]);
}
}
}
}
int main()
{
freopen("1.in","r",stdin);
get(n);
rep(2,n,i)
{
int x,y,z;
get(x);get(y);get(z);
add(x,y,z);add(y,x,z);
}
rep(1,n,i)a[i]=read()*1.0/100;
dfs(1,0);dp(1,0,0);
printf("%.6lf",ans);return 0;
}