【洛谷】P3244[HNOI2015]落忆枫音

首先没有环的方案数是很好求的

根据朱刘算法的推论，一个 DAG 中存在一个点能够到达每一个点，那么每个点都选一条入边一定能构成一个树型图（有向树）

所以DAG可以直接乘法原理

考虑有环的情况

只要将总方案数减去非法方案数就好了

非法方案数是什么呢

首次加入的这条边一定是环上的一条边，所以一定存在一条或者多条回路从 t 回到 s

设构造路径 t 到 u 的方案数为 G(u)，那么 u 的后继节点 v 的方案数是

那么

解释一波柿子 1：由于当前已经在 t，所以 t 的出边是一定的，所以要除掉 t 的度数

解释一波柿子 2：由于 v 的入边的选择对于每一种方案是一定的，所以要除去 v 的度数，然后加法原理搞定

建反向边就可以更方便推柿子了