【BZOJ3566】概率充电器（SHOI2014）-树形DP+概率DP

测试地址：概率充电器
做法：本题需要用到树形DP+概率DP。
要求保持充电状态的点的期望数目，根据期望的线性性，我们可以求出每个点保持充电状态的概率 $p_{i}$ ，然后累加起来。但是我们发现这样的话状态转移方程十分复杂，所以考虑反过来求，求每个点没有被充电的概率。
令 $d o w n (i)$ 为点 $i$ 不被它自己和它子树中的点充电的概率，因为一个点的一个儿子不给它充电有两种情况，一是它的儿子本身就没被充电，二是它的儿子被充电但边未通电，所以我们有：
$d o w n (i) = (1 - q_{i}) \prod_{j \in s o n (i)} d o w n (j) + (1 - d o w n (j)) (1 - P_{(i, j)})$
再令 $u p (i)$ 为点 $i$ 不被它的父亲充电的概率，这时也有两种情况，一是它的父亲本身没被充电，二是它的父亲被充电但它们之间的边未通电。那么我们首先算出它的父亲没被充电的概率：
$t = u p (f a (i)) \frac{d o w n (f a (i))}{d o w n (i) + (1 - d o w n (i)) (1 - P_{(f a (i), i)})}$
注意这里的除法是因为我们要排除点 $i$ 的贡献，要注意特判分母等于 $0$ 的情况，如果它等于 $0$ ，就直接意味着 $t = 0$ 。接下来我们有：
$u p (i) = t + (1 - t) (1 - P_{(f a (i), i)})$
那么最后的答案就是：
$a n s = \sum_{i = 1}^{n} (1 - d o w n (i) u p (i))$
听说有可能爆栈，所以DP还是用BFS做更为稳妥一些。
题外话：感觉这种复杂的DP转移题目还是很难理解，特别是还和概率和树扯在一起，非常考验人的大脑……
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
int n,first[500010]={0},tot=0,fa[500010],h,t,order[500010];
double q[500010],down[500010],up[500010],ep[500010];
struct edge
{
    int v,next;
    double p;
}e[1000010];

void insert(int a,int b,double p)
{
    e[++tot].v=b;
    e[tot].p=p;
    e[tot].next=first[a];
    first[a]=tot;
}

void init()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int a,b;
        double p;
        scanf("%d%d%lf",&a,&b,&p);
        insert(a,b,p/100.0),insert(b,a,p/100.0);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&q[i]);
        q[i]/=100.0;
    }
}

void bfs()
{
    h=t=order[1]=1;
    fa[1]=0;
    while(h<=t)
    {
        int v=order[h++];
        for(int i=first[v];i;i=e[i].next)
            if (e[i].v!=fa[v]) fa[e[i].v]=v,ep[e[i].v]=e[i].p,order[++t]=e[i].v;
    }
}

void dp()
{
    for(int i=n;i>=1;i--)
    {
        int v=order[i];
        down[v]=1.0-q[v];
        for(int j=first[v];j;j=e[j].next)
            if (e[j].v!=fa[v]) down[v]*=down[e[j].v]+(1.0-down[e[j].v])*(1.0-e[j].p);
    }
    for(int i=1;i<=n;i++)
    {
        int v=order[i];
        if (v==1) {up[v]=1.0;continue;}
        up[v]=down[v]+(1.0-down[v])*(1.0-ep[v]);
        up[v]=fabs(up[v])<1e-6?0.0:up[fa[v]]*down[fa[v]]/up[v];
        up[v]=up[v]+(1.0-up[v])*(1.0-ep[v]);
    }
    double ans=0.0;
    for(int i=1;i<=n;i++)
        ans+=1.0-down[i]*up[i];
    printf("%.6lf",ans);
}

int main()
{
    init();
    bfs();
    dp();

    return 0;
}