树上概率与换根。

Table of Contents

  1. Description
  2. Solution

Description

Given a tree with probability of charging $P$ for every vertex and edge.

Evaluate the expection of number of charged vertexes.

Solution

A vertex can be charged both from its subtree and its ancestors.

Thus we split the calculation into two steps, as a common method.

However, calculating the probability of being charges would be lunatic. Therefore we turn to being not charged.

First evaluate $f[i]$, for the probability of not charging vertex $i$ with its subtrees. we can get:

$\begin{align}f[i] = (1 - q[x]) \times \prod_{y \in S}{f[y] + (1 - ep_k)(1 - f[y])} \end{align}$, where $k$ as the edge connecting $i$ and $y$.

The exprssion has two parts, for each son being uncharged and being charged but the edge is not available.

Then we need to calculate how its father will affect it. we get:

$g[i] = (\frac{g[fa]}{x_i} + (1 - \frac{g[fa]}{x_i})(1 - ep_k)) \times f[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
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef double db;

const int maxn = 5e+5 + 5;

struct edge
{
    int to, nxt; db v;
}e[maxn << 1];
int n, ptr, lnk[maxn];
db f[maxn], g[maxn], q[maxn];

inline void add(int bgn, int end, db val)
{
    e[++ptr] = (edge){end, lnk[bgn], val}; lnk[bgn] = ptr;
}
inline int rd()
{
    register int x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = x * 10 + (c ^ 48), c=  getchar();
    return x;
}
void dfs(int x, int fa)
{
    f[x] = 1.0;
    for(int p = lnk[x]; p; p = e[p].nxt)
    {
        int y = e[p].to;
        if(y == fa) continue;
        dfs(y, x);
        f[x] *= ((1.0 - e[p].v) * (1.0 - f[y]) + f[y]);
    }
    f[x] *= (1.0 - q[x]);
}
void efs(int x, int fa, int ine)
{
    if(!fa)
    {
        g[x] = f[x];
        for(int p = lnk[x]; p; p = e[p].nxt)
        {
            int y = e[p].to;
            efs(y, x, p);
        }
    }
    else
    {
        db kx = ((1 - e[ine].v) * (1 - f[x]) + f[x]);
        g[x] = f[x] * ((g[fa] / kx) + (1 - g[fa]/kx) * (1 - e[ine].v));
        for(int p = lnk[x]; p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(y == fa) continue;
            efs(y, x, p);
        }
    }   
}

int main()
{
    n = rd();
    for(int i = 1; i < n; ++i)
    {
        int u = rd(), v = rd(); db pi = rd();
        pi *= 0.01;
        add(u, v, pi); add(v, u, pi);
    }
    for(int i = 1; i <= n; ++i)
        q[i] = rd(), q[i] *= 0.01;
    dfs(1, 0);
    efs(1, 0, 0);
    db sum = 0.0;
    for(int i = 1; i <= n; ++i) sum += (1 - g[i]);
    printf("%.6lf\n", sum);
    return 0;
}