BZOJ3566【SHOI2014】概率充电器 <概率DP+树形DP>

Problem

【SHOI2014】概率充电器

$\mathrm{Time\;Limit:\;40\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

著名的电子产品品牌$\mathrm{SHOI}$刚刚发布了引领世界潮流的下一代电子产品——概率充电器：
“采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决定！$\mathrm{SHOI}$概率充电器,您生活不可或缺的必需品！能充上电吗？现在就试试看吧！”
$\mathrm{SHOI}$概率充电器由$n-1$条导线连通了$n$个充电元件。进行充电时，每条导线是否可以导电以概率决定，每一个充电元件自身是否直接进行充电也由概率决定。
随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为$\mathrm{SHOI}$公司的忠实客户，你无法抑制自己购买$\mathrm{SHOI}$产品的冲动。在排了一个星期的长队之后终于入手了最新型号的$\mathrm{SHOI}$概率充电器。
你迫不及待地将$\mathrm{SHOI}$概率充电器插入电源——这时你突然想知道，进入充电状态的元件个数的期望是多少呢？

Input

第一行一个整数$n$表示概率充电器的充电元件个数，充电元件由$1\sim n$编号。
之后的$n-1$行每行三个整数$a, b, p$，描述了一根导线连接了编号为$a$和$b$的充电元件，通电概率为$p\%$。
第$n+2$行$n$个整数$q_i$。表示$i$号元件直接充电的概率为$q_i\%$。

Output

输出一行一个实数，为进入充电状态的元件个数的期望，四舍五入到六位小数。

Sample Input

3
1 2 50
1 3 50
50 0 0

Sample Output

1.000000

HINT

对于$100\%$的数据，$n\le5\times10^5$，$0\le p,q_i\le100$。

Source

By 佚名提供

标签：概率DP 树形DP

Solution

期望$\mathrm{DP}$。
$w_{u,v}$：$(u,v)$通电的概率。
$f_u$：$u$没通电的概率。

1. 防止$u$自己供电：
   显然$u$自己不供电的概率为

   $$f_u=1-p_u$$

2. 防止通过$u$的儿子$\lbrace v\rbrace$对其供电：
   对于一个儿子$v$，其通电的概率为$1-f_v$，向$u$通电的概率为$w_{u,v}\times(1-f_v)$
   于是

   $$f_u=f_u\times\prod(1-w_{u,v}\times(1-f_v))$$

   从儿子向父亲$\mathrm{DP}$即可。

3. 防止通过$u$的儿子$fa$对其供电：
   对于$fa$，如果由其向$u$供电，那么其一定不能由$u$向其供电。$fa$不考虑$u$供电时，不通电的概率为$\frac{f_{fa}}{1-w_{fa,u}\times(1-f_u)}$，则通电概率为$1-\frac{f_{fa}}{1-w_{fa,u}\times(1-f_u)}$，能供电到$u$的概率为$w_{fa,u}\times(1-\frac{f_{fa}}{1-w_{fa,u}\times(1-f_u)})$
   于是

   $$f_u=f_u\times(1-w_{fa,u}\times(1-\frac{f_{fa}}{1-w_{fa,u}\times(1-f_u)}))$$

   从父亲向儿子$\mathrm{DP}$即可。

进行两次$\mathrm{DFS}$即可得到$f_u$的值，答案为每个点通电的期望之和，即$\sum_{i=1}^{n}1-f_i$。
时间复杂度$O(n)$。

Code

#include <bits/stdc++.h>
#define EPS 1e-8
#define MAX_N 500000
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n; dnt f[MAX_N+5];
vector <int> G[MAX_N+5];
vector <dnt> E[MAX_N+5];
void DFS(int u, int fa) {
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i]; dnt w = E[u][i];
        if (v ^ fa) DFS(v, u), f[u] *= 1-w*(1-f[v]);
    }
}
void DFS(int u, int fa, dnt w) {
    if (fa && 1-w*(1-f[u]) >= EPS)
        f[u] *= 1-w*(1-f[fa]/(1-w*(1-f[u])));
    for (int i = 0, v; i < (int)G[u].size(); i++)
        if ((v = G[u][i]) ^ fa) DFS(v, u, E[u][i]);
}
int main() {
    read(n); dnt ans = 0;
    for (int i = 1, u, v, c; i < n; i++)
        read(u), read(v), read(c), 
        G[u].push_back(v), E[u].push_back(1.0*c/100), 
        G[v].push_back(u), E[v].push_back(1.0*c/100);
    for (int i = 1, p; i <= n; i++)
        read(p), f[i] = 1-1.0*p/100;
    DFS(1, 0), DFS(1, 0, 0);
    for (int i = 1; i <= n; i++) ans += 1-f[i];
    return printf("%.6lf\n", ans), 0;
}