[SHOI2014] 概率充电器

首先因为每个点的贡献都是 \(1\)，所以求的就是概率。

每个点都有三种来电的原因：

1. 自己发电
2. 由儿子那边来电
3. 由父亲那边来电

前两种好办，只要树形 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);
}

原文地址：http://www.cnblogs.com/cc0000/p/16818031.html