按层把概率推到下一层

解题套路

1. 先把图画成「节点 + 有向边」。原题的图常常是绕来绕去的管子、交错的木钉、来回跳的状态， 看不出哪两条汇到一起；重画成节点与箭头之后，只剩两种局部结构：
   • 分叉：一条进、两条出；
   • 汇合：两条进、一条出。
2. 给每个节点记一个数 $w$：从入口出发、到达该节点的概率。 入口记 $w=1$。
3. 按拓扑序往下推，只用两条规则：
   • 过分叉：把 $w$ 按各支的概率分掉（左右等可能就各 $\dfrac{w}{2}$）——分步乘法；
   • 过汇合：把汇进来的各条边的数相加——分类加法（两条边互斥）。 规则就这两条，没有第三条。
4. 推到出口，读数。全部出口的 $w$ 之和必须是 $1$——这是免费的自查。
5. 要期望就再乘一层：每个出口挂一个取值，$E=\sum w_i x_i$。

关键是第 3 步的顺序：一个汇合口必须等它的所有入边都算完才能往下推。 所以先分层（或按拓扑序），别看见一条边就往下跑。

它和「逐条枚举路径」的分工

同一张图有两种算法，结果当然一样，成本不一样：

分叉不多（三五条路）时枚举更直观，也便于互相验算；一旦图有汇合、层数一多， 按层推进是唯一不会算崩的那条路——它就是把「路径求和」里的公共前缀提取了出来， 和递推数列省掉重复计算是同一件事。

常见失手

• 汇合口没收齐就往下推：只把先算出来的那条边推下去，另一条到得晚，结果整支概率少一半。 对策：先按层排好，同一层全算完再进下一层。
• 把汇合当成分叉：汇合口是相加，不是再除以 $2$。看清箭头方向：两条进、一条出的是汇合。
• 忘了「汇合之后还可能再分叉」：一个节点既收两条边又往下分两条，两件事都要做，顺序是先加后分。
• 出口概率和不为 $1$ 就说明漏了边或多算了边——推完一定要加一次。