首先因为每个点的贡献都是 \(1\),所以求的就是概率。
每个点都有三种来电的原因:
- 自己发电
- 由儿子那边来电
- 由父亲那边来电
前两种好办,只要树形 DP 一次就够了。
第三种的话就需要重新做了。
设 \(f_{i}\) 为被充电的概率。
现在设 \(u\) 为父亲,\(v\) 为儿子,我们想要从父亲转移到儿子。
当前的 \(f_u\) 有一部分是从 \(v\) 直接转移过去的,所以不能直接算。
设 \(x\) 为 \(f_u\) 中不是 \(v\) 产生的贡献。
只要把 \(x\) 解出来就行了。
\(f_{u}=x+(1-x)\times f_v\times val_i\)。
这样就能计算 \(u\) 对 \(v\) 的贡献了。
#include <bits/stdc++.h>
using namespace std;
const int maxn=500002;
const int maxm=1000020;
typedef double db;
int to[maxm],nxt[maxm],head[maxn],num;db val[maxm];
void add(int x,int y,db v){num++;to[num]=y;val[num]=v;nxt[num]=head[x];head[x]=num;}
int n,m;
db f[maxn];
void dfs1(int p,int fa)
{
for(int i=head[p];i;i=nxt[i])
{
int v=to[i];
if(v==fa) continue;
dfs1(to[i],p);
f[p]+=(1-f[p])*val[i]*f[v];
}
}
void dfs2(int p,int fa)
{
for(int i=head[p];i;i=nxt[i])
{
int v=to[i];
if(v==fa) continue;
if(fabs(1-f[v]*val[i])<1e-8)
{
dfs2(to[i],p);
continue;
}
f[v]+=(1-f[v])*(f[p]-f[v]*val[i])/(1-f[v]*val[i])*val[i];
dfs2(to[i],p);
}
}
int main()
{
// freopen("p.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y,p;scanf("%d%d%d",&x,&y,&p);
double q=p*0.01;
add(x,y,q); add(y,x,q);
}
for(int i=1;i<=n;i++)
{
int p;scanf("%d",&p);
f[i]=p*0.01;
}
dfs1(1,0);
dfs2(1,0);
db ans=0;
for(int i=1;i<=n;i++)
ans+=f[i];
printf("%.6lf",ans);
}
标签:head,概率,充电器,val,int,db,num,maxm,SHOI2014
From: https://www.cnblogs.com/cc0000/p/16818031.html