题目链接[SHOI2014]概率充电器 woc我的高考概率是怎么学的这么简单的概率公都忘了233 公式：设事件A,B，p为概率，则 p(A|B)=p(A)+p(B)-p(A&B) 意思是发生A或B事件之一的概率是发生A的概率+发生B的概率-A和B同时发生概率 那么一个点x有电的情况为1:自己给自己充上了电；2:子节点给他充上了电；3：父节点给他充上了电 设事件1的概率为p[x]，那么1、2使得x有电的概率可以直接使用公式dfs求出来 现在考虑3，我们从父节点贡献到子节点时要把子节点贡献给父节点的贡献减去，公式变一下形即可算出 然后在正向用公式合并即可 注意除法的时候判断除数大小，被坑了 #include #include #include #include #include using namespace std; const int maxn=500010; int n,m,tot=1,h[maxn]; struct edge{int to,next; double w;}G[maxn*2]; double p[maxn],dp[maxn]; void dfs1(int x,int fat){ for (int i=h[x];i;i=G[i].next){ int v=G[i].to; if (v==fat) continue; dfs1(v,x); p[x]=p[x]+p[v]*G[i].w-p[x]*p[v]*G[i].w;//p(A|B)=p(A)+p(B)-p(A&B); } } void dfs2(int x,int fat){ for (int i=h[x];i;i=G[i].next){ int v=G[i].to; if (v==fat) continue; double tmp=1-p[v]*G[i].w; if (abs(tmp)<1e-10) dp[v]=1;//这里要注意 else{ double tmp2=(dp[x]-p[v]*G[i].w)/tmp; dp[v]=p[v]+tmp2*G[i].w-p[v]*tmp2*G[i].w; } dfs2(v,x); } } void add(int x,int y,double z){ G[++tot].to=y;G[tot].next=h[x];h[x]=tot;G[tot].w=z; G[++tot].to=x;G[tot].next=h[y];h[y]=tot;G[tot].w=z; } int main(){ scanf("%d",&n); for (int i=1;i