LibreOJ 2192 「SHOI2014」概率充电器

一道不算太难的概率树形 DP？
此处每个结点贡献都是 1，所以相当于算概率。

设 ai=qi，valu,v 表示 u,v 连边的通电概率，soni 表示 i 的儿子的集合。
再设 fi 表示 i 不被子树内的结点供电的概率，gi 表示 i 不被祖先供电的概率。

首先有转移 fp=(1−ap)∏v∈sonp(fv+(1−fv)(1−valp,v))

考虑到 p 本身也属于自己的子树，所以先保证 p 自己不供电。
然后 ∀v∈sonp，要么自己也不从子树供电，要么自己从子树供电但是边不导电。
易得上式。

接着有 P=fp⋅gpfv+(1−fv)(1−valp,v)gv=P+(1−P)(1−valp,v)(v∈sonp)

同样有两种情况，父节点不供电或者父节点供电但是不导电。
那么我们考虑算出 P 即父节点不供电的概率。
显然它不能从子树中供电也不能从父节点的祖先供电，即 fp⋅gp。
而且 v 的贡献要删去。

同时注意根节点的 g 值为 1。

统计答案时，即 n∑i=1(1−fi⋅gi)。
因为从祖先或是从子树两者都满足它才没电。

代码：

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