Description
给你一张 n 个点 m 条边的DAG，1 号节点没有入边。再向这个DAG中加入边 x→y ，求形成的新图中以 1 为根的外向树形图数 模 10^9+7 。
Input
输入文件的第一行包含四个整数 n、m、x和y，依次代表枫叶上的穴位数、脉络数，以及要添加的脉络是从穴位 x连向穴位y的。 接下来 m行，每行两个整数，由空格隔开，代表一条脉络。第 i 行的两个整数为ui和vi，代表第 i 条脉络是从穴位 ui连向穴位vi的。
Output
输出一行，为添加了从穴位 x连向穴位 y的脉络后，枫叶上以穴位 1 为根的脉络树的方案数对 1,000,000,007取模得到的结果。
Sample Input
4 4 4 3
1 2 1 3 2 4 3 2Sample Output
3
HINT
对于所有测试数据，1 <= n <= 100000，n - 1 <= m <= min(200000, n(n -1) / 2)，
1 <= x, y, ui, vi <= n。
Solution
直接处理外向树形图的数目比较困难，考虑容斥，用 每个点选一条入边的方案数 减去 每个点选一条入边形成不了外向树形图的方案数 得到答案。
每个点选一条入边的方案数直接求 对于无法形成外向树形图的情况显然是出现了一个环（除自环）而我们知道x和y显然就在环中，那么我们只需要从y到x跑一个拓扑排序+dp求出y到x的路径数所占总路径数的比例即可Code
//By Menteur_Hxy#include#include #include #include #include #include #include #define F(i,a,b) for(register int i=(a);i<=(b);i++)using namespace std;typedef long long LL;int read() { int x=0,f=1; char c=getchar(); while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();} while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar(); return x*f;}const int N=100010,MOD=1000000007;bool vis[N];LL ans,du[N],f[N],de[N];vector V[N];queue Q;LL qpow(LL a,LL b) { LL t=1; while(b) { if(b&1) t=t*a%MOD; a=a*a%MOD; b>>=1; } return t;}void dfs(int x) { int siz=V[x].size(); F(i,0,siz-1) if(!vis[V[x][i]]) vis[V[x][i]]=1,dfs(V[x][i]);}int main() { int n=read(),m=read(),s=read(),t=read(),u,v; ans=du[1]=1; du[t]++; F(i,1,m) u=read(),v=read(),V[u].push_back(v),du[v]++; F(i,1,n) ans=ans*du[i]%MOD,du[i]=qpow(du[i],MOD-2); vis[t]=1; dfs(t); F(i,1,n) { int siz=V[i].size(); F(j,0,siz-1) if(vis[i]&&vis[v=V[i][j]]) de[v]++; } f[t]=du[t]; Q.push(t); while(!Q.empty()) { u=Q.front(); Q.pop(); int siz=V[u].size(); F(i,0,siz-1) if(vis[v=V[u][i]]) { f[v]=(f[v]+f[u]*du[v])%MOD; de[v]--; if(!de[v]) Q.push(v); } } printf("%lld",ans*(1-f[s]+MOD)%MOD); return 0;}