BZOJ

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.