题解
考虑 (u) 进入充电状态需要满足两种条件之一： (exists v in mathrm{subtree}(u)) 直接充电， (exists v
ot in mathrm{subtree}(u)) 直接充电。
这是一个很显然的换根dp。
考虑事件 (A) 或 (B) 发生的概率 (P(A+B) = P(A) + P(B) - P(AB)= P(A) + P(B) - P(A) imes P(B)) 。
（不是直接加起来啊！）
设 (f(u)) 为 (u) 进入充电状态的概率 ， (g(u)) 为 (u) 的子树使 (u) 进入通电状态的概率。
（这里先将题目中的 (p_{u,v},q_u) 除以 (100) ）
刚开始令 (g(u) gets q_i) ，对于 (u) 的每一个儿子 (v) ，再使 (g(u) gets g(u) + g(v) imes p_{u,v} - g(u) imes g(v) imes p_{u,v}) 。
然后是二次扫描。设 (f_v(u)) 为 (u) 不通过 (v) 的子树进入充电状态的概率，容易得到 (f(u) = f_v(u) + g(u) imes p_{u,v} - f_v(u) imes g(u) imes p_{u,v}) 。
整理得到 (f_v(u) = dfrac{f(u) - g(v) imes p_{u,v}}{1 - g(v) imes p_{u,v}}) 。
然后像之前一样， (f(v) gets f_v(u) imes p_{u,v} + g(v) - f_v(u) imes p_{u,v} imes g(v)) 。
注意若 (1 - f(v) imes p_{u,v} = 0) ，则直接令 (f(v) gets g(v)) 。
其实当 (1 - f(v) imes p_{u,v} = 0) 时， (f(v) = p_{u,v} = 1) ， (v) 是一定会充电的，所以无法用 (f(u)) 求出 (f_v(u)) ，而且也没有更新 (f(v)) 的必要。
#include <cstdio>
#define MAX_N (500000 + 5)
const int eps = 1e-6;
int n;
int h[MAX_N], tot;
struct Edge {
int to, next;
double p;
} e[MAX_N << 1];
int q[MAX_N];
double f[MAX_N];
void Add_Edge(int u, int v, int w) {
e[++tot].to = v;
e[tot].p = w * 0.01;
e[tot].next = h[u];
h[u] = tot;
}
void DFS1(int u, int fa) {
f[u] = q[u] * 0.01;
int v;
double p;
for (int i = h[u]; i; i = e[i].next) {
v = e[i].to;
if (v == fa) continue;
DFS1(v, u);
p = f[v] * e[i].p;
f[u] = f[u] + p - f[u] * p;
}
}
void DFS2(int u, int fa) {
int v;
double p;
for (int i = h[u]; i; i = e[i].next) {
v = e[i].to;
if (v == fa) continue;
if (f[v] * e[i].p - 1 > eps || 1 - f[v] * e[i].p > eps) {
p = (f[u] - f[v] * e[i].p) / (1 - f[v] * e[i].p) * e[i].p;
f[v] = f[v] + p - f[v] * p;
}
DFS2(v, u);
}
}
int main() {
scanf("%d", &n);
int u, v, w;
for (int i = 1; i < n; ++i) {
scanf("%d%d%d", &u, &v, &w);
Add_Edge(u, v ,w);
Add_Edge(v, u, w);
}
for (int i = 1; i <= n; ++i)
scanf("%d", &q[i]);
DFS1(1, 0);
DFS2(1, 0);
double ans = 0;
for (int i = 1; i <= n; ++i)
ans += f[i];
printf("%.6lf
", ans);
return 0;
}
当然，也可以考虑补集。
设 (f(u)) 为 (u) 不进入充电状态的概率 ， (g(u)) 为 (u) 的子树使 (u) 不进入通电状态的概率。
则 (g(u) = (1-q_u)prodlimits_{vinmathrm{son}(u)}(1 - p_{u,v} + p_{u,v} imes g(v))) 。
然后就是套路， (f(v) = g(v) imes left(1 - p_{u,v} + p_{u,v} imes dfrac{f(u)}{1 - p_{u,v} + p_{u,v} imes g(v)}
ight)) 。
则 (ans = sumlimits_{i=1}^{n}(1-f(i))) 。
#include <cstdio>
#define MAX_N (500000 + 5)
const int eps = 1e-6;
int n;
int h[MAX_N], tot;
struct Edge {
int to, next;
double p;
} e[MAX_N << 1];
int q[MAX_N];
double f[MAX_N];
void Add_Edge(int u, int v, int w) {
e[++tot].to = v;
e[tot].p = w * 0.01;
e[tot].next = h[u];
h[u] = tot;
}
void DFS1(int u, int fa) {
f[u] = 1 - q[u] * 0.01;
int v;
for (int i = h[u]; i; i = e[i].next) {
v = e[i].to;
if (v == fa) continue;
DFS1(v, u);
f[u] *= 1 - e[i].p + f[v] * e[i].p;
}
}
void DFS2(int u, int fa) {
int v;
double p;
for (int i = h[u]; i; i = e[i].next) {
v = e[i].to;
if (v == fa) continue;
p = f[u] / (1 - e[i].p + f[v] * e[i].p);
f[v] *= 1 - e[i].p + p * e[i].p;
DFS2(v, u);
}
}
int main() {
scanf("%d", &n);
int u, v, w;
for (int i = 1; i < n; ++i) {
scanf("%d%d%d", &u, &v, &w);
Add_Edge(u, v ,w);
Add_Edge(v, u, w);
}
for (int i = 1; i <= n; ++i)
scanf("%d", &q[i]);
DFS1(1, 0);
DFS2(1, 0);
double ans = 0;
for (int i = 1; i <= n; ++i)
ans += 1 - f[i];
printf("%.6lf
", ans);
return 0;
}