• \(\text{HNOI2015}\) 落忆枫音

题目：

给一个 \(n\) 个点 \(m\) 条边的 DAG，点 \(1\) 的入度为 \(0\)。随后向图中再加入一条有向边，加边后图可能不再是 DAG。

求出图中有多少个 \(n-1\) 条有向边的集合，满足只使用集合中的边能从
\(1\) 到达其它所有点（即有向生成树），模 \(10^9+7\)

\(n≤10^5,m≤2×10^5\)

题解：

新加入的边是特殊的，因为如果加入了那么原图就有可能不是 DAG。

加入了新边的影响就是原来的图不再是一个 DAG，而有可能会出现环。

不妨容斥一下。

在 DAG 上做有向生成树很简单。如此题，此时的答案为：

\[ans=\prod_{i=2}^{n}in_i \]

其中 \(in_i\) 表示 \(i\) 号节点的入边。

这个结论显然，答案就是所有节点（除了 \(1\) 号）的入边数量之积。（就是给每个节点选一个父亲）

接下来考虑环。

设加入的边为 \(s\to t\)，那么新出现的环只可能是从 \(t\to \dots \to s\)。（因为原来的图没有环，所以只可能是新增的边形成了环）

此时我们可以用一个 dfs 来对其进行一个朴素的搜索。

考虑对于搜到每个点的情况，不妨设 \(f_i\) 表示到了 \(i\) 点时有多少种无用情况（即环），那么答案显然就是 \(ans-f_t\)

考虑这个 dp，易知

\[f_i=\dfrac{\prod\limits_{i=2}^{n}in_i}{in_s\times \prod\limits_{i=1}^{k}in_{a_i}} \]

所以转移显然：

\[f_i=\dfrac{1}{in_i}\sum_{(i,j)}f_j \]

那么在 DAG 上套就可。