BZOJ 3566

传送门

BY wyfcyx

直接求充上电的概率好复杂,那么我们考虑求充不上电的概率

这个概率可以分为两部分:儿子没法给它充电的概率和爸爸没法给它充电的概率,设分别为$f_{i,0}$和$f_{i,1}$,可以用两遍dfs搞出来

首先考虑它的儿子给它充不上电的情况,即为每个儿子的$P_{儿子没电}+P_{儿子有电但边没电啊}$的乘积再乘上这个点自己没电的概率(公式中点和边的概率都用$P$来表示了,请注意区分)

$f_{i,0}=(1−P_i)\prod_{j{\in}son(i)}(f_{j,0}+(1−f_{j,0})∗(1−P_{Edge_{i,j}}))$

下面考虑爸爸没法给它充电的情况,设$P’$为除掉$x$对它爸爸影响后$fa_x$没充上电的概率,就是$P_{下面没电且除掉x的影响}*P_{上面没电}$

$P’=\frac{f_{fa_x,0}}{f_{x,0}+(1−f_{x,0})∗(1−P_{Edge(x,fa_x)})}∗f_{fa_x,1}$

然后$x$上面充不上电的概率就很容易得出了 就是$P_{儿子乖,爹没电}+P_{爹有电但边没电啊}$

$f_{x,1}=P’+(1−P’)∗(1−P_{Edge(x,fa_x)})$

最终每个节点$i$被充电的概率$g_i=1−f_{i,0}∗f_{i,1}$

$ans=\sum_{i=1}^{n}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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
program bzoj_3566;
var l:array[1..1000000]of record ed,pre:longint; p:extended; end;
lst,fa:array[1..500000]of longint;
f1,f2:array[1..500000]of extended;
n,i,a,b,c,tot:longint;
ans:extended;
procedure link(a,b,p:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
l[tot].p:=p/100;
end;
procedure dfs1(t:longint);
var k:longint;
begin
k:=lst[t];
while k<>0 do
begin
if l[k].ed<>fa[t] then
begin
fa[l[k].ed]:=t;
dfs1(l[k].ed);
f1[t]:=f1[t]*(f1[l[k].ed]+(1-f1[l[k].ed])*(1-l[k].p));
end;
k:=l[k].pre;
end;
end;
procedure dfs2(t:longint);
var k:longint;
p:extended;
begin
k:=lst[t];
while k<>0 do
begin
if l[k].ed<>fa[t] then
begin
p:=f1[l[k].ed]+(1-f1[l[k].ed])*(1-l[k].p);
if p<1e-6 then p:=0 else p:=f1[t]*f2[t]/p;
f2[l[k].ed]:=p+(1-p)*(1-l[k].p);
dfs2(l[k].ed);
end;
k:=l[k].pre;
end;
end;
begin
readln(n);
tot:=0;
for i:=1 to n-1 do
begin
readln(a,b,c);
link(a,b,c);
link(b,a,c);
end;
for i:=1 to n do
begin
read(c);
f1[i]:=1-c/100;
end;
fa[1]:=0;
dfs1(1);
f2[1]:=1;
dfs2(1);
ans:=0;
for i:=1 to n do ans:=ans+1-f1[i]*f2[i];
writeln(ans:0:6);
end.