[题解] [HNOI2015]落忆枫音
题意
给一张 (n) 个点 (m) 条边的 (DAG) ,保证点 (1) 不存在入边,现在需要在 (DAG) 中加入一条不在原图中的边 ((x,y)) ,求这个有向图以 (1) 为根的树形图个数对 (1e9+7) 取模的结果。
（而且有点像是骗狗进来杀）
范围
(1 le n le 100000, n−1 le m le min(200000 , frac{2n(n−1)}{2} ),1 le x,y,u_i,v_i le n)
题解
先假设我们没有加上 ((x,y)) 这条边，那么可以比较简单的知道总方案数, (r_i) 为入度数量
[ans= prod^{n}_{i=1}r_i
]
接下来，我们来看看加上 ((x,y)) 的限制后，答案该怎么统计。
显然只会增加一些非法的情况，我们只要减去这些非法情况就OK了。
假设存在一个环，显然不合法的情况都在环上的点产生的。
我们设这些点为 (a_1,a_2, a_k)
那么不合法的情况为：
[frac{ans}{prod^k_{i=1}r_i}
]
又由于环的入度已经确定，那么其他的可选随意选择。
设 (f_v) 记录从 (y) 到 (v) 的 (frac{ans}{prod^k_{i=1}r_i}) 的值
为为那么转移方程为：
[f[u]=sum f[v]
]
最后的答案为：
[ans=prod^n_{i=1}(i==y)? r_{i+1} : r_i - f_x
]