这是一道概率+树形$dp$

首先我们看到这里每一个的贡献都是1,所以我们要求的期望就是概率

求得其实就是这个

$$\sum_{i=1}^nP_i$$

$P_i$为节点$i$通电的概率

显然节点$i$通电有三种可能

  1. 它自己来电了

  2. 它的子树里有一个点来电了传了过来

  3. 它的子树外面有一个点来电了传了过来

第一种情况最好考虑了,至于第二种和第三种我们好像很难解决的样子

但是这显然也告诉了我们这是一个套路题,第二种和第三种正好就是树规里的$up$ $and$ $down$思想

于是我们设$h[i]$表示第$i$个节点通电的概率,之后我们利用$up$ $and$ $down$思想,在第一遍dfs的过程中,$h[i]$表示$i$通电的概率,且电一定来自它自己或者它的子树里(对应第一第二种情况),在第二遍dfs的时候被更新成为电来自于任何地方的概率(对应所有情况)

最开始初始化,$h[i]=a[i]*0.01$电只能来自自己

之后第一遍dfs,树形dp里的$up$,我们要将子树的信息合并给根,由于根通电还是有两种可能

  1. 根自己来电了

  2. 儿子来电,儿子通向根的边导电

显然这两种情况只需要满足一种就够了

但是合并之后的概率是多少呢,直接加起来显然是不对的而我还真加了起来

我们考虑有两个事件$A,B$,发生的概率分别是$P(A),P(B)$,那么至少发生一件的概率应该是

$$P(A)+P(B)-P(A)*P(B)$$

这个怎么推出来的,很简单,至少发生一件,那么就有三种可能

  1. $A$发生$B$不发生,那么则为$P(A)*(1-P(B))$

  2. $B$发生$A$不发生,那么则为$P(B)*(1-P(A))$

  3. $A,B$一起发生,那么则为$P(A)*P(B)$

三项合起来最后一化就是$P(A)+P(B)-P(A)*P(B)$

所以我们合并根和子树的信息的时候,$P(A)=h[i],P(B)=h[j]*p(i,j)$,$i$是子树的根,$j$是$i$的儿子,$p(i,j)$是这条边导电的概率

所以$h[i]=P(A)+P(B)-P(A)*P(B)$

之后我们就要考虑$down$了,一个节点有点也有可能来自它的父亲,于是我们采用$down$的思想用父亲更新儿子

显然我们更新一位父亲的某个儿子,显然我们只能用其他点来电传到父亲的概率来更新这个儿子

于是我们设$P(B)=h[j]*p(i,j)$,而且有

$$P(A)+P(B)-P(A)*P(B)=h[i]$$

我们要求的是$P(A)$即除了$j$这棵子树其他点来电使得$i$有电的概率

于是解一下这个方程

$$P(A)-P(A)*P(B)=h[i]-P(B)$$

$$P(A)*(1-P(B))=h[i]-P(B)$$

$$P(A)=\frac{h[i]-P(B)}{1-P(B)}$$

而之后我们去更新儿子的话还有一边是否导电需要考虑,于是

$$h[j]=h[j]+(P(A)*p(i,j))-h[j]*P(A)*p(i,j)$$

之后就没有啦,同时还有一个非常坑的地方就是如果$P(B)=h[j]*p(i,j)=1$

那么除以$1-P(B)$肯定会出错,由于$h[j]$都已经是1了,显然没有什么必要去更新它了,于是可以直接跳过这一层接着往下更新就好了

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define maxn 500005
#define eps 1e-7
struct node
{
    int v,nxt,w;
}e[maxn<<1];
int num,n,m;
int a[maxn],head[maxn],deep[maxn];
double h[maxn];
double ans;
inline int read()
{
    char c=getchar();
    int x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')
      x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
inline void add_edge(int x,int y,int z)
{
    e[++num].v=y;
    e[num].nxt=head[x];
    e[num].w=z;
    head[x]=num;
}
void dfs(int x)//up
{
    for(re int i=head[x];i;i=e[i].nxt)
    if(!deep[e[i].v])
    {
        deep[e[i].v]=deep[x]+1;
        dfs(e[i].v);
        double k=h[e[i].v]*double(e[i].w)/100;
        h[x]=h[x]+k-h[x]*k;
    }
}
inline int check(double aa,double bb)
{
    if(aa+eps>bb&&aa-eps<bb) return 1;
    return 0;
}
void redfs(int x)//down
{
    ans+=h[x];
    for(re int i=head[x];i;i=e[i].nxt)
    if(deep[e[i].v]>deep[x])
    {
        if(check(h[e[i].v]*double(e[i].w)/100,1)) 
        {
            redfs(e[i].v);
            continue;
        }
        double k=(h[x]-h[e[i].v]*double(e[i].w)/100)/(1-h[e[i].v]*double(e[i].w)/100);
        k*=double(e[i].w)/100;
        h[e[i].v]=h[e[i].v]+k-k*h[e[i].v];
        redfs(e[i].v);
    }
}
int main()
{
    n=read();
    int x,y,z;
    for(re int i=1;i<n;i++)
    {
        x=read();
        y=read();
        z=read();
        add_edge(x,y,z),add_edge(y,x,z);
    }
    for(re int i=1;i<=n;i++)
        a[i]=read(),h[i]=a[i]*0.01;
    deep[1]=1;
    dfs(1);
    redfs(1);
    printf("%.6lf",ans);
    return 0;
}