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

这是一道概率+树形$dp$ 首先我们看到这里每一个的贡献都是1，所以我们要求的**期望就是概率** 求得其实就是这个 $$\sum_{i=1}^nP_i$$ $P_i$为节点$i$通电的概率 显然节点$i$通电有三种可能 1. 它自己来电了 1. 它的子树里有一个点来电了传了过来 1. 它的子树外面有一个点来电了传了过来 第一种情况最好考虑了，至于第二种和第三种我们好像很难解决的样子 但是这显然也告诉了我们这是一个套路题，第二种和第三种正好就是树规里的$up$ $and$ $down$思想 于是我们设$h[i]$表示第$i$个节点通电的概率，之后我们利用$up$ $and$ $down$思想，在第一遍dfs的过程中，$h[i]$表示$i$通电的概率，且电一定来自它自己或者它的子树里（对应第一第二种情况），在第二遍dfs的时候被更新成为电来自于任何地方的概率（对应所有情况） 最开始初始化，$h[i]=a[i]*0.01$电只能来自自己 之后第一遍dfs，树形dp里的$up$，我们要将子树的信息合并给根，由于根通电还是有两种可能 1. 根自己来电了 1. 儿子来电，儿子通向根的边导电 显然这两种情况只需要满足一种就够了 但是合并之后的概率是多少呢，直接加起来显然是不对的~~而我还真加了起来~~ 我们考虑有两个事件$A,B$，发生的概率分别是$P(A),P(B)$，那么至少发生一件的概率应该是 $$P(A)+P(B)-P(A)*P(B)$$ 这个怎么推出来的，很简单，至少发生一件，那么就有三种可能 1. $A$发生$B$不发生，那么则为$P(A)*(1-P(B))$ 1. $B$发生$A$不发生，那么则为$P(B)*(1-P(A))$ 1. $A,B$一起发生，那么则为$P(A)*P(B)$ 三项合起来最后一化就是$P(A)+P(B)-P(A)*P(B)$ 所以我们合并根和子树的信息的时候，$P(A)=h[i],P(B)=h[j]*p(i,j)$，$i$是子树的根，$j$是$i$的儿子,$p(i,j)$是这条边导电的概率 所以$h[i]=P(A)+P(B)-P(A)*P(B)$ 之后我们就要考虑$down$了，一个节点有点也有可能来自它的父亲，于是我们采用$down$的思想用父亲更新儿子 显然我们更新一位父亲的某个儿子，显然我们只能用其他点来电传到父亲的概率来更新这个儿子 于是我们设$P(B)=h[j]*p(i,j)$，而且有 $$P(A)+P(B)-P(A)*P(B)=h[i]$$ 我们要求的是$P(A)$即除了$j$这棵子树其他点来电使得$i$有电的概率 于是解一下这个方程 $$P(A)-P(A)*P(B)=h[i]-P(B)$$ $$P(A)*(1-P(B))=h[i]-P(B)$$ $$P(A)=\frac{h[i]-P(B)}{1-P(B)}$$ 而之后我们去更新儿子的话还有一边是否导电需要考虑，于是 $$h[j]=h[j]+(P(A)*p(i,j))-h[j]*P(A)*p(i,j)$$ 之后就没有啦，同时还有一个非常坑的地方就是如果$P(B)=h[j]*p(i,j)=1$ 那么除以$1-P(B)$肯定会出错，由于$h[j]$都已经是1了，显然没有什么必要去更新它了，于是可以直接跳过这一层接着往下更新就好了 ```cpp #include<iostream> #include<cstring> #include<cstdio> #define re register #define maxn 500005 #define eps 1e-7 struct node { int v,nxt,w; }e[maxn<<1]; int num,n,m; int a[maxn],head[maxn],deep[maxn]; double h[maxn]; double ans; inline int read() { char c=getchar(); int x=0; while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar(); return x; } inline void add_edge(int x,int y,int z) { e[++num].v=y; e[num].nxt=head[x]; e[num].w=z; head[x]=num; } void dfs(int x)//up { for(re int i=head[x];i;i=e[i].nxt) if(!deep[e[i].v]) { deep[e[i].v]=deep[x]+1; dfs(e[i].v); double k=h[e[i].v]*double(e[i].w)/100; h[x]=h[x]+k-h[x]*k; } } inline int check(double aa,double bb) { if(aa+eps>bb&&aa-eps<bb) return 1; return 0; } void redfs(int x)//down { ans+=h[x]; for(re int i=head[x];i;i=e[i].nxt) if(deep[e[i].v]>deep[x]) { if(check(h[e[i].v]*double(e[i].w)/100,1)) { redfs(e[i].v); continue; } double k=(h[x]-h[e[i].v]*double(e[i].w)/100)/(1-h[e[i].v]*double(e[i].w)/100); k*=double(e[i].w)/100; h[e[i].v]=h[e[i].v]+k-k*h[e[i].v]; redfs(e[i].v); } } int main() { n=read(); int x,y,z; for(re int i=1;i<n;i++) { x=read(); y=read(); z=read(); add_edge(x,y,z),add_edge(y,x,z); } for(re int i=1;i<=n;i++) a[i]=read(),h[i]=a[i]*0.01; deep[1]=1; dfs(1); redfs(1); printf("%.6lf",ans); return 0; } ```