关键词：
Description
著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器:
“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!
”
SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。
随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。
作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。
你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?
Input
第一行一个整数:n。概率充电器的充电元件个数。充电元件由 1-n 编号。
之后的 n-1 行每行三个整数 a, b, p,描述了一根导线连接了编号为 a 和 b 的
充电元件,通电概率为 p%。
第 n+2 行 n 个整数:qi。表示 i 号元件直接充电的概率为 qi%。
Output
输出一行一个实数,为进入充电状态的元件个数的期望,四舍五入到六位小数
Sample Input
1 2 50
1 3 50
50 0 0
Sample Output
HINT
对于 100%的数据,n≤500000,0≤p,qi≤100。
做一个转化，转化为求不能进入充电状态的概率，最后用1减去即可
那么设 \(f[x]\) 表示x不能被进入充电状态的概率，先考虑子树内部：
\(f[x]=(1-q[i])*\prod{((1-f[u])*(1-p[i])+f[u])}\)
上面的转移方程意思为分两种情况：
1.子节点内部没有进入充电状态 \(f[u]\)
2.子节点内部已经进入充电状态，但是边断掉了 \((1-f[u])*(1-p[i])\)
最后从根下放再做一遍即可
转载于巨佬PI sonhttp://www.cnblogs.com/Yuzao/p/7679317.html
喻队太巨了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 struct Node 7 { 8 int next,to; 9 double dis; 10 }edge[1000001]; 11 int num,head[500001]; 12 double f[500001],ans,c[500001]; 13 void add(int u,int v,double d) 14 { 15 num++; 16 edge[num].next=head[u]; 17 head[u]=num; 18 edge[num].to=v; 19 edge[num].dis=d; 20 } 21 void dfs1(int x,int fa) 22 {int i; 23 f[x]=1-c[x]; 24 for (i=head[x];i;i=edge[i].next) 25 { 26 int v=edge[i].to; 27 if (v==fa) continue; 28 dfs1(v,x); 29 f[x]*=(1-edge[i].dis)*(1-f[v])+f[v]; 30 } 31 } 32 void dfs2(int x,int fa) 33 {double tmp; 34 int i; 35 for (i=head[x];i;i=edge[i].next) 36 { 37 int v=edge[i].to; 38 if (v==fa) continue; 39 tmp=(1-edge[i].dis)*(1-f[v])+f[v]; 40 tmp=f[x]/tmp; 41 f[v]*=(1-edge[i].dis)*(1-tmp)+tmp; 42 dfs2(v,x); 43 } 44 } 45 int main() 46 {int i,n,u,v; 47 double p; 48 cin>>n; 49 for (i=1;i<=n-1;i++) 50 { 51 scanf("%d%d%lf",&u,&v,&p); 52 add(u,v,p/100.0); 53 add(v,u,p/100.0); 54 } 55 for (i=1;i<=n;i++) 56 scanf("%lf",&c[i]),c[i]/=100.0; 57 dfs1(1,1); 58 dfs2(1,1); 59 for (i=1;i<=n;i++) 60 ans+=1.0-f[i]; 61 printf("%.6lf\n",ans); 62 }
loj#2192.「shoi2014」概率充电器(代码片段)
Loj#2192.「SHOI2014」概率充电器题目描述著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器：「采用全新纳米级加工技术，实现元件与导线能否通电完全由真随机数决定！SHOI概率充电器，您生活不... 查看详情
p4284[shoi2014]概率充电器(代码片段)
P4284[SHOI2014]概率充电器链接：https://www.luogu.org/problemnew/show/P4284题目描述著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器：“采用全新纳米级加工技术，实现元件与导线能否通电完全由真随... 查看详情
bzoj3566:[shoi2014]概率充电器
...SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI概率充电器由n-... 查看详情
bzoj3566[shoi2014]概率充电器树形概率dp
...刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI概率充... 查看详情
bzoj3566:[shoi2014]概率充电器
...充电状态？【题解】引用自：【BZOJ3566】【SHOI2014】概率充电器树形DP概率DP by 空灰冰魂最大的难点在于计算每个点充电期望时，两个节点各自的期望都会影响对方的期望。所以考虑转化对象，改为求每个节点充不上电的... 查看详情
[shoi2014]概率充电器(代码片段)
...生都能看懂（大佬就是大佬啊）：题解P4284【[SHOI2014]概率充电器】，第二次dp的状态方程真的很妙啊。刚开始我总按照套路想设\(dp[u]\)表示\(u\)的子树的期望，看完题解后发现这是没有依据的，因为每一个元件可以直接充电，不... 查看详情
bzoj3566[shoi2014]概率充电器
...刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数 查看详情
●bzoj3566[shoi2014]概率充电器
题链：http://www.lydsy.com/JudgeOnline/problem.php?id=3566题解：概率dp，树形dp 如果求出每个点被通电的概率t， 那么期望答案就是t1×1+t2×1+t3*1+...+tn×1 现在问题就是要去求每个点被通电的概率。 因为是一颗树，所以每个点是否... 查看详情
shoi2014概率充电器(代码片段)
题目链接：戳我非常不好意思，因为想要排版，所以今天先只把代码贴出来，明天补题解。QAQ#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#defineeps1e-7#defineMAXN500010intn,m,t;in 查看详情
bzoj3566:[shoi2014]概率充电器树形概率dp(代码片段)
设g[u]为这个点被儿子和自己充上电的概率，f[u]为被儿子、父亲和自己充上电的概率然后根据贝叶斯公式（好像是叫这个），1.P(A+B)=P(A)+P(B)-P(A)*P(B)，2.P(A)=(P(A+B)-P(B))/(1-P(B))g的转移很好想，根据上面的1公式，g[u]=g[u]+g[e[i].to]*e[i].p-g... 查看详情
解题：shoi2014概率充电器(代码片段)
题面显然就是在求概率，因为期望乘的全是1.。。。然后就推推推啊设$fgg[i]$表示这个点父亲没给他充上电的概率，$sgg[i]$表示这个点子树(和它自己没给他充上电的概率)，然后这个点没充上电的概率就是$fgg[i]*sgg[i]$我们发现我们... 查看详情
[bzoj3566][shoi2014]概率充电器(代码片段)
传送门DescriptionSHOI概率充电器由n-1条导线连通了n个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元... 查看详情
[题解]luogup4284[shoi2014]概率充电器(代码片段)
https://www.luogu.com.cn/problem/P4284比较套路的概率题？由期望的线性性可以把每个点拆开来，然后答案就是每个点通电的概率之和。通电的概率并不怎么好算，我们可以算点(u)不通电的概率(f[u])，然后答案就是[sumlimits_i=1^n1-f[i]]发现... 查看详情
bzoj3566
3566:[SHOI2014]概率充电器TimeLimit: 40Sec MemoryLimit: 256MBSubmit: 982 Solved: 422[Submit][Status][Discuss]Description著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全 查看详情
bzoj3566概率充电器（动态规划）
【BZOJ3566】概率充电器（动态规划）题面BZOJDescription著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您... 查看详情
shoi2002百事世界杯之旅|概率论(代码片段)
题目：SHOI2002若当前已经有了x种，再买一个买到不一样的概率为(n-x)/n，要使这个概率变成1，则至少再买n/(n-x)瓶。1#include<cstdio>2#include<string>34longlongmax(longlongx,longlongy)5returny<x?x:y;678longlonggcd(longlongx,longlongy 查看详情
cogs1224.[shoi2002]百事世界杯之旅（期望概率）
COGS1224.[SHOI2002]百事世界杯之旅★ 输入文件：pepsi.in 输出文件：pepsi.out 简单对比 时间限制：1s 内存限制：128MB 【问题描述】 “……在2002年6月之前购买的百事任何饮料的瓶盖上都... 查看详情
p1291[shoi2002]百事世界杯之旅（概率）(代码片段)
P1291[SHOI2002]百事世界杯之旅设$f(n,k)$表示共n个名字,剩下k个名字未收集到，还需购买饮料的平均次数则有：$f(n,k)=fracn-kn*f(n,k)+frackn*f(n,k+1)+1$移项整理，可得：$f(n,k)=f(n,k+1)+fracnk$根据递推式，可得：$f(n,0)=nsum_k=1^nfrac1k$蓝后g 查看详情