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

· · 题解

严格来讲算是换根dp？

直接来讲做法好了……

本题题解

首先题目中要求期望，那么其实就是每个点被充电的概率加在一起

现在问题是要求每个点被充电的概率……

(容我去扯几句废话，想看题解的话跳过好了)

这里想讲一个关于概率题的小技巧，就是关于如何求某个事件发生的概率P，事实上大家也清楚，除了一些特殊的近似算法之外，我们在程序中计算概率的方法无非就是加减乘除四则运算而已……而减法和除法又是加法和乘法的逆。

而在概率角度上，应该各位都是知道乘法原理和加法原理的，乘法意味着独立事件，而加法意味着互斥事件……，另外一个概率中很常见的等式是所有事件发生的概率和等于1

因此概率上来讲，如果剔除掉近似算法的话，我们其实只有3个方程可以使用(这里不讨论条件概率……)

1.乘法原理

2.加法原理

3.所有概率和等于1

因此我们在求概率的过程本质上就是在做一件事，将这个事件拆分成若干个要么独立要么互斥的事件，然后期间可能需要使用若干次求补事件的转化……

所以我们对于这道题来讲我们也是采取类似的拆分做法，下面详细的讲下如何拆分~

首先题目中给出的一个点被充电的条件是自己有电或周边点有电且连接的边导电吗，注意到或的关系不可以用乘法原理描述，因此我们取补之后变化为且的关系，所以只需要求出来每个点没电的概率，然后用1去减就是了

那么现在我们观察每个点不被充电的概率了，由于这是一只树，所以我们先计算出不被子树内部点充电的概率是多少，然后再去考虑子树外部点进行充电的情况……，那么我们令Dp_{i}表示i不被自己子树内点充电的概率

那么由于一个点i要想没电必须保证自己不被子树中的任意一个点充电，所以只需要求出来每个子树无法给i充电的概率然后乘到一起就好了，当然，还要乘上i自己没电的概率

现在的问题是，什么时候点v没法给i充电？，有两种情况，1.点v没电，2.点v有电且边不导电，这两种情况显然互斥，所以可以加起来

所以我们可以列出来这样一个转移方程？(P_{i},val_{i,j}分别表示i有电的概率和i，j导电的概率)

Dp_{i}=(1-P_{i})\prod_{v∈i.son}Dp_{v}+(1-Dp_{v})(1-val_{i,v})

现在该考虑被子树外的点充上电的概率了，我们发现，子树外边的点想要给i充上电，必须经过i的父亲边，所以呢我们发现可以删掉这父亲边，然后整棵树分裂为两个子树，其中一颗就是i的子树，另一颗就是所谓的“子树外边的树”，对着这棵树来一遍刚才的树形dp，最后这个点没电概率大概就是两边都不能充上电的概率乘起来，同时还是对father有没有电分情况讨论，然后加在一起，式子的话大概长这样，会发现他和刚才的dp式子非常像,Dp_{i}^{'}表示重新dp之后的结果

Dp_{i}(Dp_{fa{i}}^{'}+(1-Dp_{fa_{i}}^{'})(1-val_{i,fa_{i}}))

换句话来讲，就是如果这个i是整棵树的根的话，直接跑刚才的dp就可以了，但是我们发现直接跑刚才的dp复杂度是O(N^2)的，因此我们考虑换根dp，但是发现直接换根还是没有办法做，好吧我们把整个dp拆成两部分，一个是换根之后不用动的部分(子树)，另一部分是换根之后需要动的部分(外边的连通块)，然后换根之后需要动的部分可以dp来求……

可能我刚才说的过程有点复杂，你也可以简单的理解成我们接下来要求一个点不被父亲充电的概率，但是缺点就是理解接下来推出的方程会十分别扭，因为事实上接下来的求的部分本质上就是换根dp中变动的那一部分dp值

好了不废话，我们令

Fa_{i}=Dp_{fa_{i}}^{'}+(1-Dp_{fa_{i}}^{'})(1-val_{i,fa_{i}})

那么刚才一个点没有电的概率就是Dp_{i}Fa_{i}了

其实就是一个子树多加了条边之后整体上没电的概率，其实主要也是为了写式子简洁一些

那么我们观察到在换根到v的过程中，其实新的外部连通块是由v的父亲的外部联通块加上一个v的父亲的子树刨掉v的子树构成的连通块，我们知道dp的时候是以连乘积的形式转移的，因此想要求刨掉某个子树后剩下的Dp值就直接除就可以了，最后我们将两个乘起来求出的是Dp_{v}^{'}，根据这个值计算Fa_{v}当然上述过程一看就非常的麻烦，因此为了代码好写，我们选择在dfs到v的时候就把它每个孩子的Fa计算好，然后再dfs下去

当然了式子还是要上的，由于式子摞在一起过于恶心，只给出求Dp_{i}^{'}的式子

Dp_{i}^{'}=\frac{Fa_{fa_{i}}Dp_{fa_{i}}}{Dp_{i}+(1-Dp_{i})(1-val_{i,fa_{i}})}

然后去求Fa_{i}就行了~

(我知道设一堆变量然后倒来倒去非常没人性，但是概率题就是这样……不倒式子说不清楚意义……，凑合着看吧)

(其实代码贼短,代码31行题解71行)

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=5*1e5+10;typedef double db;db st[N];db res;int n;
int v[2*N];int x[2*N];db val[2*N];int al[N];int ct;bool book[N];db son[N];db fa[N];
inline void add(int u,int V,db va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;}
inline void dfs1(int u)//求出dp
{
    book[u]=true;son[u]=1.0-st[u];
    for(int i=al[u];i;i=x[i])
    {
        if(book[v[i]]){continue;}dfs1(v[i]);
        son[u]*=son[v[i]]+(1.0-son[v[i]])*(1.0-val[i]);
    }book[u]=false;
}
inline void dfs2(int u)//求出Fa
{
    book[u]=true;
    for(int i=al[u];i;i=x[i])
    {
        if(book[v[i]]){continue;}
        db p=fa[u]*son[u]/(son[v[i]]+(1.0-son[v[i]])*(1.0-val[i]));//求出Dp’
        fa[v[i]]=p+(1.0-p)*(1.0-val[i]);dfs2(v[i]);//然后计算Fa
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1,u,v,va;i<n;i++){scanf("%d%d%d",&u,&v,&va);add(u,v,va/100.0);add(v,u,va/100.0);}
    for(int i=1,va;i<=n;i++){scanf("%d",&va);st[i]=va/100.0;}fa[1]=1;//1是乘法0元
    dfs1(1);dfs2(1);for(int i=1;i<=n;i++){res+=1-fa[i]*son[i];}printf("%lf",res);return 0;//拜拜程序~
}