标题 from 题目背景。
题意:给你一个 DAG 然后在这个图上加一条边,加完之后不一定是 DAG。求满足如下条件的树的数量:
- 每个父亲到它的儿子们都有一条边。
先考虑是一个 DAG 的情况。发现答案即为 \(\prod in_i\)。原因显然。
麻烦的情况是它不是 DAG。发现多出来的非法的情况即为选出了一个环。但是加上这一条边之后可能有不止一个环,不能直接枚举环。但是发现一个环 \(C\) 贡献的非法情况有 \(\dfrac{\prod in_i}{\prod_{j\in C} in_j}\)。这可以进行一个 dp 的解决。方程即为 \(dp_v=\sum_{(u,v)\in E}dp_u\times\dfrac{1}{in_u}\)。求逆元解决即可。
标签:DAG,一个,dfrac,离开,无论如何,情况,prod,dp,不会 From: https://www.cnblogs.com/yinhee/p/luo_yi_feng_yin.html