class="markdown_views prism-atom-one-light"> 题目链接 题意：
给你一棵树，树上每一个点一开始有一定概率有电，并且边会导电，每条边又一个导电的概率。求导电完毕后有电的点的个数的期望。$n<=500000$ 题解：
一道不错的题。 我们首先的一个考虑是想利用期望的线性性来对整棵树进行树形dp。我们设$dp[x]$为点$x$有电的概率，然后转移的化分从子树和从父节点两种情况，用经典的两遍dfs的方法，第一遍从子树到父节点，第二遍从父节点到子树。从父节点转移的时候要去掉这个子树的贡献。于是在第一遍的时候有$dp[x]=sum dp[y]*p$，其中$p$表示两边导电的概率，第二遍是$dp[x]+=(dp[fa[x]]-dp[x]*p)*p$。然后就做完了。好，你是不是也这么想的？看上去很有道理啊。有没有什么问题啊？ 有！你这样算会遇到这样一个问题，就是你一个点有电的概率可能大于1！你可能会想，那还不简单，转移的时候和1取min啊。看起来又对了是不是？还是不对！你有没有好好想想为什么概率会比1大啊。原因是，这个点有电，有以下两种情况：本身有电、相连的节点有电并且从导线导电过来了。但是这些事情并不是相互独立的，是可能同时发生的，可能本身有电，又同时从好几个节点导过来了点，像一开始那样求的应该是这个点的期望充电次数。可能同时发生的话你的同一个事件对答案就贡献了好几遍，所以会算出来答案比正确答案大，甚至出现算出的概率大于1的情况，所以这里的概率是不能直接累加的。那该怎么办？ OI有一个经典的思想，就是正难则反！
我们考虑一个点没有电的概率，一个点没有点的情况是，这个点本身没有电，并且所有与它相连的点都没有把电导过来。有没有发现什么不一样？之前是两个条件任意一个发生，就会有电，任意一个这个条件会导致很多重复统计，但是这里却是两个条件同时满足！同时满足就意味着不存在什么重复贡献答案了，此时我们是要求这两个条件同时发生的概率。很明显，自己没有电和周围的电没有把电导过来是两个独立的事件，所以概率可以直接相乘得出答案。此时我们就可以使用刚才是树形dp的思想，两遍dfs来统计答案了。正确的dp方程应该是，在第一遍的时候：$dp[x]=(1-x本身带电的概率)prod(dp[y]+(1-dp[y])*(1-边导电的概率))$。第二遍的时候$x$的贡献是乘给了父节点，于是父节点除以$x$的贡献就好了，我们把父节点去掉$x$之后没有电的概率记作$g$，那么$g=(dp[fa[x]/(dp[x]+(1-dp[x])*(1-边导电的概率)))*$，然后$dp[x]*=g+(1-g)*(1-边导电的概率)$就可以了。
这样就真的做完了。 代码： #include using namespace std; int n,hed[500010],cnt,fa[500010]; double dp[500010],ans; const double eps=1e-8; struct node { int to,next; double dis; }a[2000010]; inline void add(int from,int to,double dis) { a[++cnt].to=to; a[cnt].dis=dis; a[cnt].next=hed[from]; hed[from]=cnt; } inline void dfs(int x) { for(int i=hed[x];i;i=a[i].next) { int y=a[i].to; if(y==fa[x]) continue; fa[y]=x; dfs(y); dp[x]*=dp[y]+(1.0-dp[y])*(1.0-a[i].dis); } } inline void dfs2(int x) { for(int i=hed[x];i;i=a[i].next) { int y=a[i].to; if(y==fa[x]) continue; double ji=dp[x]/(dp[y]+(1.0-dp[y])*(1.0-a[i].dis)); dp[y]*=ji+(1.0-ji)*(1.0-a[i].dis); dfs2(y); } } int main() { scanf("%d",&n); for(int i=1;i<=n-1;++i) { int x,y,z; scanf("%d%d%d",&x,&y,&z); double gg=(double)z/100; add(x,y,gg); add(y,x,gg); } for(int i=1;i<=n;++i) { scanf("%lf",&dp[i]); dp[i]/=100; dp[i]=1.0-dp[i]; } dfs(1); dfs2(1); for(int i=1;i<=n;++i) ans+=1-dp[i]; printf("%.6lf ",ans); return 0; }