LibreOJ 2192 「SHOI2014」概率充电器

一道不算太难的概率树形 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)\)。
因为从祖先或是从子树两者都满足它才没电。

代码：

#include <cstdio>
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);
}