BZOJ 3566 [SHOI2014]概率充电器

题目大意

给你一棵树，树上每个节点有$p_i$的可能性通电，每条边有$q_i$的可能性是联通的，如果一个点是通电的，那么与他相连的通过联通边抵达的未通电的点也会通电。求通电点数的期望.

这道题一看就是概率DP……因为好多点都可能自通电，所以不能用简单的普通树形DP……考虑换根DP.

首先求的是总通电点数的期望，可以转化成每个点通电的概率和。

首先考虑一个点被子树供电的概率。因为一个点有多个儿子所以求的是这些儿子中任意一个点为其供电的概率。这样需要大量的容斥比较复杂所以可以转化成求一个点不被任意一个儿子或自己供电的概率，之后用1减一下就可以了。

不被子树供电的概率很好求，设$f_i$为所求，此时有$f_i = \prod\limits_{i \to j} f_j + (1 - f_j)(1 - q_{i \to j})$

接下来考虑被父树不供电的概率。

一号点作为树根肯定有$g_1 = 1$了。之后对于每个点，它不被父树供电的概率就是它本身不被子树供电或自供电且它的父亲本身不被子树供电或自供电或者被供电但是不连通的概率。注意这里要求自己不自供电所以需要进行一步容斥。

$$g_i = (1 - q_{fa_i \to i}) + q_{fa_i \to i}(g_{fa_i} \frac{f_{fa_i}}{f_i + (1-f_i)(1-q_{fa_i \to i})})$$

最后每个节点被供电的概率就是$1 - f_i g_i$

附上另外一位聚聚的题解，里面写了另一种DP方程，感觉比较好理解qwq

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define R register
#define N 500010
int n,ix,iy;
int to[N<<1],nxt[N<<1],head[N],tot;
double iz,q[N],val[N<<1],f[N],g[N],ans;
inline void AE(R int tx,R int ty,R double tz){to[++tot]=ty,val[tot]=tz,nxt[tot]=head[tx],head[tx]=tot;}
void DFSA(R int pos,R int pre)
{
	f[pos]=1.0-q[pos];
	for(R int i=head[pos];i;i=nxt[i]) if(to[i]!=pre) DFSA(to[i],pos),f[pos]*=f[to[i]]+(1.0-f[to[i]])*(1.0-val[i]);
}
void DFSB(R int pos,R int pre,R double V)
{
	g[pos]=(1-V)+V*g[pre]*f[pre]/(f[pos]+(1-f[pos])*(1-V));
	for(R int i=head[pos];i;i=nxt[i]) if(to[i]!=pre) DFSB(to[i],pos,val[i]);
}
inline char nc()
{
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int RI()
{
	R int ret=0;R char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp^'0'),tmp=nc();
	return ret;
}
int main()
{
	scanf("%d",&n);
	for(R int i=2;i<=n;++i) ix=RI(),iy=RI(),iz=1.0*RI()/100,AE(ix,iy,iz),AE(iy,ix,iz);
	for(R int i=1;i<=n;++i) q[i]=1.0*RI()/100;
	DFSA(1,0);
	g[1]=1;
	for(R int i=head[1];i;i=nxt[i]) DFSB(to[i],1,val[i]);
	for(R int i=1;i<=n;++i) ans+=1.0-f[i]*g[i];
	printf("%.6lf\n",ans);
	return 0;
}