设 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[u]*g[e[i].to]*e[i].p
然后因为 root 没有父亲, 所以 f[root]=g[root]
然后是 f 的转移, 首先看父亲可以充电到儿子的概率 = 父亲能充上电的概率 - 父亲被儿子充上电的概率, 根据上面的 2 公式也就是 nw=(f[u]-g[e[i].to]*e[i].p)/(1.0-g[e[i].to]*e[i].p)
然后转移就很好做了, 和 g 是一样的: f[e[i].to]=g[e[i].to]+nw*e[i].p-g[e[i].to]*nw*e[i].p;
- #include<iostream>
- #include<cstdio>
- using namespace std;
- const int N=500005;
- int n,m,h[N],cnt;
- double g[N],f[N],ans;
- struct qwe
- {
- int ne,to;
- double p;
- }e[N<<1];
- int read()
- {
- int r=0,f=1;
- char p=getchar();
- while(p>'9'||p<'0')
- {
- if(p=='-')
- f=-1;
- p=getchar();
- }
- while(p>='0'&&p<='9')
- {
- r=r*10+p-48;
- p=getchar();
- }
- return r*f;
- }
- void add(int u,int v,double w)
- {
- cnt++;
- e[cnt].ne=h[u];
- e[cnt].to=v;
- e[cnt].p=w;
- h[u]=cnt;
- }
- void dfs1(int u,int fa)
- {
- for(int i=h[u];i;i=e[i].ne)
- if(e[i].to!=fa)
- {
- dfs1(e[i].to,u);
- g[u]=g[u]+g[e[i].to]*e[i].p-g[u]*g[e[i].to]*e[i].p;
- }
- }
- void dfs2(int u,int fa)
- {
- ans+=f[u];
- for(int i=h[u];i;i=e[i].ne)
- if(e[i].to!=fa)
- {
- if(1.0-g[e[i].to]*e[i].p==0.0)
- f[e[i].to]=1;
- else
- {
- double nw=(f[u]-g[e[i].to]*e[i].p)/(1.0-g[e[i].to]*e[i].p);
- f[e[i].to]=g[e[i].to]+nw*e[i].p-g[e[i].to]*nw*e[i].p;
- }
- dfs2(e[i].to,u);
- }
- }
- int main()
- {
- n=read();
- for(int i=1;i<n;i++)
- {
- int x=read(),y=read(),z=read();
- add(x,y,(double)z/100.0),add(y,x,(double)z/100.0);
- }
- for(int i=1;i<=n;i++)
- g[i]=read(),g[i]/=100.0;
- dfs1(1,0);
- f[1]=g[1];
- dfs2(1,0);
- printf("%.6f\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2771270.html