正題

題目鏈接:https://www.luogu.com.cn/problem/P4284

---

題目大意

$n$個(gè)點(diǎn)的一棵樹，每個(gè)點(diǎn)有$p_i$概率通電，每個(gè)邊有一定概率可以導(dǎo)電。求期望有電的節(jié)點(diǎn)個(gè)數(shù)。

---

解題思路

發(fā)現(xiàn)考慮通電概率很難，所以我們可以考慮不通電的概率。

如果只是計(jì)算一個(gè)點(diǎn)的話很方便，我們統(tǒng)計(jì)一下以一個(gè)點(diǎn)為根時(shí)候每個(gè)點(diǎn)的通電概率$f_i$即可。

有轉(zhuǎn)移方程$$f_x=(1?p_x)?\prod (f_y+(1?f_y)?(1?w))$$

然后換根計(jì)算即可。

時(shí)間復(fù)雜度$O(n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=5e5+10; struct node{int to,next;double w; }a[N*2]; int n,tot,ls[N]; double f[N],g[N],p[N],ans; void addl(int x,int y,double w){a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot;return; } void dfs(int x,int fa){f[x]=1.0-p[x]; for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;dfs(y,x);f[x]*=f[y]+(1.0-f[y])*(1.0-a[i].w);}return; } void dp(int x,int fa){for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;double k=g[x]/(f[y]+(1.0-f[y])*(1-a[i].w));g[y]=f[y]*(k+(1.0-k)*(1.0-a[i].w));dp(y,x);}ans+=g[x];return; } int main() {scanf("%d",&n);for(int i=1;i<n;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);addl(x,y,(1.0*w)/100.0);addl(y,x,(1.0*w)/100.0);}for(int i=1;i<=n;i++)scanf("%lf",&p[i]),p[i]/=100;dfs(1,1);g[1]=f[1];dp(1,1);printf("%lf",n-ans); return 0;}

總結(jié)

以上是生活随笔為你收集整理的P4284-[SHOI2014]概率充电器【树形dp,换根法,数学期望】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。