目录
显示
题目链接
https://www.luogu.com.cn/problem/P4284
题解
设 \(f_i\) 表示 \(i\) 号点没有电的概率(这样设式子会更简洁些)。则答案显然是 \(\sum_{i=1}^n 1-f_i\)。
我们随便定一个点作为根,这样一个点没电,需要同时满足三个条件:
- 这个点本身没电;
- 这个点的所有子节点都不传电;
- 这个点的父节点不传电;
先考虑前两种情况,第三种情况我们可以通过换根的方式处理。
第一次 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; }