Rockdu's Blog

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

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

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

对于 100%的数据,n≤500000,0≤p,qi≤100。

首先将无根树化为有根树，这样的话，我们可以把每一个点被冲上电的概率分成被父亲充电的概率和被儿子充电的概率。但是我们发现这样不仅不好统计概率，而且不能简单相加（可以同时被充电）。这时候不妨换一个角度考虑：计算因为父亲充不上电的概率和因为儿子充不上电的概率。这样相当于原来的补集，就可以相加了。

考虑u因为儿子x所在子树充不上电的概率：

设概率为f(x)，每一个点对父亲的贡献为h(x)，那么：

h(x) = f(x) + (1 - f(x)) * (1 - p(x, u))  (一种是自己充不上电，另一种是自己充上电了但是到父亲的导线没通，都会导致父亲没电)。

那么我们的f(u)为f(u) = h(v)(v ∈ son)，这样我们从下往上递推即可。

考虑u因为父亲d充不上电的概率g(u)：

那么有几种情况：1、父亲充不上电。2、父亲充上电但是没有导过来。第一种情况下，概率为：P1 = g(d) * (f(d) / h(u)) (相当于把u点当做父亲，d当做儿子考虑)。第二种情况下：P2 = (1 - P1) * (1 - p(u, d))，总概率P = P1 + P2。这样我们每一个点充电的概率都知道了，期望就是所有充的上电的概率相加：∑1- f(i) * g(i)

#include<cstdio>
using namespace std;
const int maxn = 5e5 + 5;
struct edge {
    int v, next;
    double w;
}e[maxn << 1];
int head[maxn], cnt, n, u, v;
void adde(const int &u, const int &v, const double &w) {
    e[++cnt] = (edge) {v, head[u], w};
    head[u] = cnt;
}
double f[maxn], g[maxn], elc[maxn], from[maxn], ans, w;
void dfs(int u, int p) {
    int v;
    f[u] = 1 - elc[u];
    for(register int i = head[u]; i; i = e[i].next) {
        v = e[i].v;
        if(v == p) continue;
        dfs(v, u);
        from[v] = e[i].w;
        f[u] *= f[v] + (1 - f[v]) * (1 - e[i].w);
    }
}
void calc(int u, int p) {
    int v;double dt;
    for(register int i = head[u]; i; i = e[i].next) {
        v = e[i].v;
        if(v == p) {continue;}
        dt = (f[u] / (f[v] + (1 - f[v]) * (1 - from[v]))) * g[u];
        g[v] = dt + (1 - dt) * (1 - from[v]);
        calc(v, u);
    }
}
int main() {
    scanf("%d", &n);
    for(register int i = 1; i < n; ++i) {
        scanf("%d%d%lf", &u, &v, &w), w /= 100;
        adde(u, v, w), adde(v, u, w);
    }
    for(register int i = 1; i <= n; ++i) 
        scanf("%lf", &elc[i]), elc[i] /= 100;
    dfs(1, 0), g[1] = 1, calc(1, 0);
    for(register int i = 1; i <= n; ++i)
        ans += 1 - f[i] * g[i];
    printf("%.6lf", ans);
    return 0;
}