[洛谷 4284,loj 2192][SHOI2014]概率充电器

题目链接

https://www.luogu.com.cn/problem/P4284

https://loj.ac/problem/2192

题解

设 \(f_i\) 表示 \(i\) 号点没有电的概率（这样设式子会更简洁些）。则答案显然是 \(\sum_{i=1}^n 1-f_i\)。

我们随便定一个点作为根，这样一个点没电，需要同时满足三个条件：

1. 这个点本身没电；
2. 这个点的所有子节点都不传电；
3. 这个点的父节点不传电；

先考虑前两种情况，第三种情况我们可以通过换根的方式处理。

第一次 dfs，我们很容易自底向上，算出所有的 \(f_i\)：

$$f_i=(1-p_i)\prod_v (f_v+(1-w_{u,v})-f_v \times (1-w_{u,v}))$$

接下来我们进行第二次 dfs，自顶向下重新计算（说白了就是将一个点的父亲节点转成这个点的子节点）即可。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
double p[500005],f[500005];
vector<pair<int,double> > e[500005];
void dfs1(int u,int fa)
{
 f[u]=(1-p[u]);
 for(auto E:e[u])
 {
  int v=E.first;
  double w=E.second;
  if(v==fa)continue;
  dfs1(v,u);
  f[u]*=(f[v]+(1-w)-f[v]*(1-w));
 }
}
void dfs2(int u,int fa)
{
 for(auto E:e[u])
 {
  int v=E.first;
  double w=E.second;
  if(v==fa)continue;
  double tmp=f[u]/(f[v]+(1-w)-f[v]*(1-w));
  f[v]*=(tmp+(1-w)-tmp*(1-w));
  dfs2(v,u);
 }
}
int main()
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<n;i++)
 {
  int u,v,p;
  scanf("%d%d%d",&u,&v,&p);
  e[u].push_back({v,p/100.0});
  e[v].push_back({u,p/100.0});
 }
 for(int i=1;i<=n;i++)
 {
  int x;
  scanf("%d",&x);
  p[i]=x/100.0;
 }
 dfs1(1,1);
 dfs2(1,1);
 double ans=0;
 for(int i=1;i<=n;i++)
  ans+=(1-f[i]);
 printf("%.6lf\n",ans);
 return 0;
}