题目

传送门

思路

笔者第一眼看到这道题，就想出了最初的DP式

\(dp_{i}\)表示i号节点亮的期望

之后顺理成章转移方程就出来了

\(dp_u=\prod(i\in son)dp_i*p_{u,i}+1*p_u+dp_{fa}*p_{fa,u}\)

但是仔细想想，这个方程是错的

因为我们从fa节点转移到u节点，这个我们转移的前提是fa是亮的，

但是我们从u转移到fa，就会发现 \(dp_{fa}\)会变小，

因为fa到u是确定这条线是好的

但是从u到fa的转移就不能确定这条线是好的

并且你会发现儿子之间有交集，每一次转移就会达到\(O(2^{son})\)的复杂度

但是我们反过来想

如果定义\(dp_{u}\)表示已u号节点为根节点的不亮的期望

\(dp_u\)的转移跟上面差不多

\(dp_u=(\prod(i\in son)(1-(1-dp_{son})*p_{u,i}))*(1-q_u)\)

之后我们考虑u的父节点是怎样转移过来的

我们设\(f_u\)为u号节点的父节点转移过来的期望

那么转移方程就可以写出来

\(f_u=1-(1-(dp_{fa}*f_{fa}/(1-(1-dp_u)*p_{fa,u})))*p_{fa,u}\)

但是我们考虑，如果以u号节点为根的子树的期望本身就是0呢？

很简单，特判就行了。

\(f_u=1-p_{fa,u}\)

那么问题又来了，精度问题怎么解决？

直接定义一个极小值就行了

答案即为\(n-\sum_{i=1}^{n}dp_i*f_i\)

笔者用cin被卡了整整半个小时

代码

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
struct node
{
    int e;
    double w;
};
int n;
double q[500005];
double dp[500005];
double f[500005];
double ans;
vector<node> g[500005];
const double eps=1e-9;
double f_abs(double x)
{
    if(x<0)
        return -x;
    return x;
}
void dfs_son(int u,int fa)
{
    f[u]=1;
    dp[u]=1-q[u];
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i].e;
        if(v!=fa)
        {
            dfs_son(v,u);
            dp[u]*=1-(1-dp[v])*g[u][i].w;
        }
    }
}
void dfs_fa(int u,int fa,double fa_w)
{
    if(f_abs(1-(1-dp[u])*fa_w)>eps)
        f[u]=1-(1-(dp[fa]*f[fa]/(1-(1-dp[u])*fa_w)))*fa_w;
    else
        f[u]=1-fa_w;
    ans-=f[u]*dp[u];
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i].e;
        if(v!=fa)
        {
            dfs_fa(v,u,g[u][i].w);
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        double w;
        scanf("%d %d %lf",&u,&v,&w);
        g[u].push_back((node){v,w/100});
        g[v].push_back((node){u,w/100});
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&q[i]);
        q[i]=q[i]/100;
    }
    ans=n;
    dfs_son(1,0);
    dfs_fa(1,0,0);
    printf("%.6lf",ans);
    return 0;
}

习题：概率充电器（数学期望）

原文：https://www.cnblogs.com/loney-s/p/12001599.html