题解 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行) 上代码~ ```C #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;//拜拜程序~ } ```