【[SHOI2014]概率充电器】解题报告

· · 题解

概率+树型dp

Part I

拿到这道题的一瞬间，反应了一下——这不是道假期望题吗？

为什么？我们考虑这道题的答案

\sum p_i*w_i

而，w_i全TMD是1 ！！！所以，就对p_i求个和就行了。

所以这题是概率dp

Part II

考虑这个dp怎么写,一片乌鸦飞过，这TM怎么写啊！！！

聪明的同学不难发现，我们任意选取一个点作为根，然后考虑每个节点，不仅它的子节点可以对它亮的概率产生贡献，它的父节点同样可以产生贡献。

这咋dp啊？这dp个p啊？

诶？好像有个做法：我们枚举每个儿子为根，然后对每种情况进行处理，每次根节点的答案是正确的，因为它没有父亲（没爹的孩子果然简单易懂呢）。复杂度O(n^2),看一眼数据范围，50w，emmm，松松松n方过百万显然过不去

考虑优化，发现每次换根的贡献只有一部分点，我们把这些点维护一下，复杂度。。。等等，这咋写啊？然后，我的思路就离正解越来越远。。。思路逐渐变态

Part III

上回书说到，每个点的概率来源有三

如果只考虑前两个，貌似dp方程比较显然

dp[now]+=(1-dp[now])\times dp[v]\times e[i].val

其中，dp[x]指点x的概率，v是now的子节点，e[i].val是连接now,v的边连通的概率

然后，考虑父节点的贡献。我们用上面dp转移出的概率从根节点向下转移，这样每个节点向下转移的时候已经是被充分计算过的，没有后效性。

感觉哪里不对。。。

以一对儿父子关系为例，a是b的父节点。第一遍dp的时候，b对a产生了贡献，第二遍dp时这个贡献又作为a的一部分贡献给了b。

发现统计重复了，我们需要的是b对a作贡献前a的dp值，换言之，即把b对a做的贡献排除出去。

考虑第一遍的dp方程

dp[a]_{now}=dp[a]_{last}+(1-dp[a]_{last})\times dp[b]\times e[i].val

每个变量的意义上同，特殊地，我们区分了dp[a]_{now}与dp[a]_{last}，分别指转移后的dp[a] (即现在已知的dp[a]) 与 转移前的dp[a] (即所求的,对dp[b] 在第二次dp中产生贡献的部分）

化简可得

dp[a]_{last}=\dfrac{dp[a]_{now}-dp[b]\times e[i].val}{1-dp[b]\times e[i].val}

求得dp_{last}后，沿用第一次的转移

dp[b]+=(1-dp[b])\times dp[a]_{last}\times e[i].val

进行第二次dp，所得的结果就是最终答案。此题完结。

另外还有一些细节见代码（当然，看完上面的那些要是自己能打出来就不要看代码了）

Part IV

又到了喜闻乐见的放代码环节

#include<bits/stdc++.h>

using namespace std;

const double eps=1e-7;

struct Edge
{
    int to,nxt;
    double val;
    Edge(){}
    Edge(int to,int nxt,double val):to(to),nxt(nxt),val(val){}
}e[1000010];
int head[500010],cnt;

void addedge(int u,int v,double val)
{
    e[++cnt]=Edge(v,head[u],val);
    head[u]=cnt;
}

int n;
double dp[500010];

void dfs1(int now,int fa)//第一遍dp
{
    for(int i=head[now];i;i=e[i].nxt)
    {
        int vs=e[i].to;
        if(fa==vs) continue;
        dfs1(vs,now);
        dp[now]+=dp[vs]*(1-dp[now])*e[i].val;
    }
}

void dfs2(int now,int fa)//第二遍dp
{
    for(int i=head[now];i;i=e[i].nxt)
    {
        int vs=e[i].to;
        if(fa==vs) continue;
        if(fabs(1-dp[vs]*e[i].val)<=eps) 
        //坑：如果分母为0直接跳过。
        //原因：分母为0说明dp[vs]为1，不需要贡献
        {
            dfs2(vs,now);
            continue;
        }
        dp[vs]+=(1-dp[vs])*(dp[now]-dp[vs]*e[i].val)/(1-dp[vs]*e[i].val)*e[i].val;
        dfs2(vs,now);
    }
}

int main()
{
    cin>>n; 
    for(int i=1;i<n;i++)
    {
        int u,v;
        double val;
        cin>>u>>v>>val;
        addedge(u,v,val/100);
        addedge(v,u,val/100);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>dp[i];//自己的贡献一开始就算进去
        dp[i]/=100;
    }
    dfs1(1,0);
    dfs2(1,0);
    double ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=dp[i];
    }
    cout<<fixed<<setprecision(6);//保留6位小数
    cout<<ans<<endl;
}

Part V

回过头来看这道题，发现我一开始的思路并没有问题，只是没想清楚。

我们统计父节点贡献的时候，本质上就是换根,把原来的父节点变成子节点，那么原来对父节点的贡献要还原，而父节点要对子节点进行贡献。而第二遍dp的本质是对重复信息的利用，以达到换根效率的最优效果——O(1)换根。

题目不错，值得一做。