传送门
概率dp好题啊。
用f[i]" role="presentation" style="position: relative;">f[i]f[i]表示i自己不亮并且子树中的节点不会让i亮的概率。
用g[i]" role="presentation" style="position: relative;">g[i]g[i]表示i的子树以外的连通块不会使i变亮的概率。
貌似f[i]" role="presentation" style="position: relative;">f[i]f[i]可以直接推出来啊：
f[i]=(1−q[i])∗∏v(f[v]+(1−f[v])∗(1−dis[i,v]))" role="presentation" style="position: relative;">f[i]=(1−q[i])∗∏v(f[v]+(1−f[v])∗(1−dis[i,v]))f[i]=(1−q[i])∗∏v(f[v]+(1−f[v])∗(1−dis[i,v]))。
g[i]" role="presentation" style="position: relative;">g[i]g[i]感觉有点难推啊。
有个坑点是我们在推g[i]的时候已经自动默认i为根的子树没亮了，因此要除一个f[i]。
然后就没啥了。
我们设一个临时变量tmp。
tmp=g[fa[i]]∗f[fa[i]]/(f[i]+(1−f[i])∗(1−dis[fa[i],i]))" role="presentation" style="position: relative;">tmp=g[fa[i]]∗f[fa[i]]/(f[i]+(1−f[i])∗(1−dis[fa[i],i]))tmp=g[fa[i]]∗f[fa[i]]/(f[i]+(1−f[i])∗(1−dis[fa[i],i]))
g[i]=tmp+(1−tmp)∗(1−dis[fa[i],i])" role="presentation" style="position: relative;">g[i]=tmp+(1−tmp)∗(1−dis[fa[i],i])g[i]=tmp+(1−tmp)∗(1−dis[fa[i],i])
代码：
#include<bits/stdc++.h>
#define N 500005
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,first[N],cnt=0;
double p[N],f[N],g[N];
struct edge{int v,next;double w;}e[N<<1];
inline void add(int u,int v,double w){e[++cnt].v=v,e[cnt].next=first[u],e[cnt].w=w,first[u]=cnt;}
inline void dfs1(int x,int fa){
f[x]=1-p[x];
for(int i=first[x];i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
dfs1(v,x),f[x]*=f[v]+(1-f[v])*(1-e[i].w);
}
}
inline void dfs2(int x,int fa){
if(x==1)g[x]=1;
for(int i=first[x];i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
double tmp=g[x]*f[x]/(f[v]+(1-f[v])*(1-e[i].w));
g[v]=tmp+(1-tmp)*(1-e[i].w);
dfs2(v,x);
}
}
int main(){
n=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
double w=read()*1.0/100;
add(u,v,w),add(v,u,w);
}
for(int i=1;i<=n;++i)p[i]=read()*1.0/100;
dfs1(1,0),dfs2(1,0);
double ans=0;
for(int i=1;i<=n;++i)ans+=1-g[i]*f[i];
printf("%.6lf",ans);
return 0;
}