BZOJ 3566.「SHOI2014」概率充电器

一道不算太难的概率树形 DP?
此处每个结点贡献都是 11,所以相当于算概率。

ai=qia_i = q_ivalu,vval_{u,v} 表示 u,vu,v 连边的通电概率,sonison_i 表示 ii 的儿子的集合。
再设 fif_i 表示 ii 不被子树内的结点供电的概率,gig_i 表示 ii 不被祖先供电的概率。

首先有转移

fp=(1ap)vsonp(fv+(1fv)(1valp,v))f_p = (1 - a_p) \prod\limits_{v \in son_p} (f_v + (1 - f_v)(1 - val_{p,v}))

考虑到 pp 本身也属于自己的子树,所以先保证 pp 自己不供电。
然后 vsonp\forall v \in son_p,要么自己也不从子树供电,要么自己从子树供电但是边不导电。
易得上式。

接着有

同样有两种情况,父节点不供电或者父节点供电但是不导电。
那么我们考虑算出 PP 即父节点不供电的概率。
显然它不能从子树中供电也不能从父节点的祖先供电,即 fpgpf_p \cdot g_p
而且 vv 的贡献要删去。

同时注意根节点的 gg 值为 11

统计答案时,即 i=1n(1figi)\sum\limits_{i = 1}^n (1 - f_i \cdot g_i)
因为从祖先或是从子树两者都满足它才没电。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
using namespace std;
const int N = 5e5;
int n;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
double val[(N << 1) + 5];
inline void add(int u,int v,double w)
{
static int tot = 0;
to[++tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot;
}
double a[N + 5],f[N + 5],g[N + 5],ans;
void dfs1(int p,int fa)
{
f[p] = 1 - a[p];
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa)
dfs1(to[i],p),f[p] *= f[to[i]] + (1 - f[to[i]]) * (1 - val[i]);
}
void dfs2(int p,int fa)
{
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa)
{
double t = f[p] * g[p] / (f[to[i]] + (1 - f[to[i]]) * (1 - val[i]));
g[to[i]] = t + (1 - t) * (1 - val[i]);
dfs2(to[i],p);
}
}
int main()
{
scanf("%d",&n);
int u,v,w;
for(register int i = 1;i < n;++i)
scanf("%d%d%d",&u,&v,&w),add(u,v,w / 100.0),add(v,u,w / 100.0);
for(register int i = 1;i <= n;++i)
scanf("%lf",a + i),a[i] /= 100;
dfs1(1,0),g[1] = 1,dfs2(1,0);
for(register int i = 1;i <= n;++i)
ans += 1 - f[i] * g[i];
printf("%.6f\n",ans);
}