【题目大意】

充电器由 n-1 条导线连通了 n 个充电元件。这n-1条导线均有一个通电概率p%,而每个充电元件本身有直接被充电的概率q[i]%。问期望有多少个充电元件处于充电状态?

【思路】

第一次做这种类型的题,还挺有意思的quq

显然这n个充电元件构成一棵树,考虑用树形DP。

我们用f1[i]表示当前元件仅仅因为直接充电或由孩子供电的概率,f2[i]表示当前元件处于充电状态的概率。

前铺两个知识点:对于两个相互独立的事件A、B,P(A+B)=P(A)+P(B)-P(A)*P(B),P(A)=(P(A+B)-P(B))/(1-P(B))。(!!)

我们可以用两次dfs求出f1、f2的值。

①对于f1,由于树中叶子节点不存在孩子,f1[叶子结点]=q[叶子结点],而对于非叶子节点,f1[i]=q[i]+∑f1[son]*p(注意这里的加法运算指代的是上述提到的概率加法)

②对于只由父亲贡献充电,我们考虑两个父子元件。对于父亲本身来说,给儿子充电的概率=总概率-儿子给自己充电的概率,pfa=f2[fa]-f1[now]*p(同样这里的减法用上面的概率加法)

f2[now]=f1[now]+pfa*p(同理这里的加法用的是上述的概率加法)

Over!!

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define EPS (1e-8)
using namespace std;
const int MAXN=+;
struct node
{
int to;
double p;
};
vector<node> E[MAXN];
double q[MAXN],f1[MAXN],f2[MAXN],ans; void addedge(int a,int b,double p)
{
E[a].push_back((node){b,p});
} bool dcmp(double a)
{
return fabs(a-)<EPS;
} void dfs1(int u,int fa)
{
for (int i=;i<E[u].size();i++)
{
int to=E[u][i].to;
if (to!=fa)
{
dfs1(to,u);
f1[u]=f1[u]+f1[to]*E[u][i].p-f1[u]*f1[to]*E[u][i].p;
}
}
} void dfs2(int u,int fa)
{
ans+=f2[u];
for (int i=;i<E[u].size();i++)
{
int to=E[u][i].to;
if (to!=fa)
{
if (dcmp(1.0-E[u][i].p*f1[to])) f2[to]=1.0;
else
{
double tmp=(f2[u]-E[u][i].p*f1[to])/(1.0-E[u][i].p*f1[to]);
f2[to]=f1[to]+tmp*E[u][i].p-f1[to]*tmp*E[u][i].p;
}
dfs2(to,u);
}
}
} void init()
{
int n;
scanf("%d",&n);
for(int i=;i<n-;i++)
{
int a,b;
double p;
scanf("%d%d%lf",&a,&b,&p);
addedge(a,b,p/);
addedge(b,a,p/);
}
for (int i=;i<=n;i++)
{
scanf("%lf",&q[i]);
f1[i]=q[i]/;
}
} void solve()
{
dfs1(,);
f2[]=f1[];
dfs2(,);
printf("%.6lf",ans);
} int main()
{
init();
solve();
return ;
}
05-11 19:32