题目描述
传送门
题目大意：一棵树，每一个点初始有一个概率为1，然后每个点可以沿着边向四周扩展，每条边有一个概率可以经过，问最终为1的点的个数的期望。
题解
f(i)表示点i从父亲扩展不到的概率，g(i)表示点i从儿子扩展不到的概率 最终的答案是 sigma 1 - f(i) * g(i) * (1-p(i)) 转移的时候，先计算出来某一个点扩展不到的概率，应该为f(i) or g(i) * 点不为1的概率，然后从某一条边过来的时候应该是 边不连通的概率 +边连通的概率 * 点扩展不到的概率
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 500005
int n,son[N],isleaf[N];
int tot,point[N],nxt[N<<
1],v[N<<
1];
double c[N<<
1];
double ans,p[N],q[N],f[N],g[N],h[N];
void add(
int x,
int y,
double z)
{
++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;
}
void dp_g(
int x,
int fa)
{
g[x]=
1.0;
for (
int i=point[x];i;i=nxt[i])
if (v[i]!=fa)
{
dp_g(v[i],x);
double now=g[v[i]]*(
1.0-p[v[i]]);
h[v[i]]=(
1.0-c[i])+c[i]*now;
g[x]*=h[v[i]];
}
}
void dp_f(
int x,
int fa)
{
son[
0]=
0;
for (
int i=point[x];i;i=nxt[i])
if (v[i]!=fa)
{
f[v[i]]=
1.0;
son[++son[
0]]=v[i],q[son[
0]]=c[i];
}
double now=
1.0;
for (
int i=
1;i<=son[
0];++i)
f[son[i]]*=now,now*=h[son[i]];
now=
1.0;
for (
int i=son[
0];i>=
1;--i)
f[son[i]]*=now,now*=h[son[i]];
for (
int i=point[x];i;i=nxt[i])
if (v[i]!=fa)
{
f[v[i]]=f[v[i]]*f[x]*(
1.0-p[x]);
f[v[i]]=(
1.0-c[i])+f[v[i]]*c[i];
dp_f(v[i],x);
}
}
int main()
{
scanf(
"%d",&n);
for (
int i=
1;i<n;++i)
{
int x,y;
double z;
scanf(
"%d%d%lf",&x,&y,&z);
add(x,y,z/
100.0),add(y,x,z/
100.0);
}
for (
int i=
1;i<=n;++i)
scanf(
"%lf",&p[i]),p[i]/=
100.0;
dp_g(
1,
0);
f[
1]=
1.0;dp_f(
1,
0);
for (
int i=
1;i<=n;++i)
ans+=
1.0-f[i]*g[i]*(
1.0-p[i]);
printf(
"%.6lf\n",ans);
}
