一道不算太难的概率树形 DP？
此处每个结点贡献都是 \(1\)，所以相当于算概率。
设 \(a_i = q_i\)，\(val_{u,v}\) 表示 \(u,v\) 连边的通电概率，\(son_i\) 表示 \(i\) 的儿子的集合。
再设 \(f_i\) 表示 \(i\) 不被子树内的结点供电的概率，\(g_i\) 表示 \(i\) 不被祖先供电的概率。
首先有转移 \[f_p = (1 - a_p) \prod\limits_{v \in son_p} (f_v + (1 - f_v)(1 - val_{p,v}))\]
考虑到 \(p\) 本身也属于自己的子树，所以先保证 \(p\) 自己不供电。
然后 \(\forall v \in son_p\)，要么自己也不从子树供电，要么自己从子树供电但是边不导电。
易得上式。
接着有 \[\begin{align*} P &= \dfrac {f_p \cdot g_p}{f_v + (1 - f_v)(1 - val_{p,v})} \\ g_v &= P + (1 - P)(1 - val_{p,v}) \\ (v &\in son_p) \end{align*}\]
同样有两种情况，父节点不供电或者父节点供电但是不导电。
那么我们考虑算出 \(P\) 即父节点不供电的概率。
显然它不能从子树中供电也不能从父节点的祖先供电，即 \(f_p \cdot g_p\)。
而且 \(v\) 的贡献要删去。
同时注意根节点的 \(g\) 值为 \(1\)。
统计答案时，即 \(\sum\limits_{i = 1}^n (1 - f_i \cdot 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
using namespace std;
const int N = 5e5;
int n;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
double val[(N << 1) + 5];
inline void add(int u,int v,double w)
{
static int tot = 0;
to[++tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot;
}
double a[N + 5],f[N + 5],g[N + 5],ans;
void dfs1(int p,int fa)
{
f[p] = 1 - a[p];
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa)
dfs1(to[i],p),f[p] *= f[to[i]] + (1 - f[to[i]]) * (1 - val[i]);
}
void dfs2(int p,int fa)
{
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa)
{
double t = f[p] * g[p] / (f[to[i]] + (1 - f[to[i]]) * (1 - val[i]));
g[to[i]] = t + (1 - t) * (1 - val[i]);
dfs2(to[i],p);
}
}
int main()
{
scanf("%d",&n);
int u,v,w;
for(register int i = 1;i < n;++i)
scanf("%d%d%d",&u,&v,&w),add(u,v,w / 100.0),add(v,u,w / 100.0);
for(register int i = 1;i <= n;++i)
scanf("%lf",a + i),a[i] /= 100;
dfs1(1,0),g[1] = 1,dfs2(1,0);
for(register int i = 1;i <= n;++i)
ans += 1 - f[i] * g[i];
printf("%.6f\n",ans);
}