首先有一个重要结论！
对于一个有向无环图（DAG），它的生成树个数就等于除根外所有点入度的乘积！
我考试的时候不知道这玩意然后直接GG了。。。
然后我们加入了一条边，可能会形成环，有环仍按以上方法计算会有不合法的情况，那么我们用总方案减去不合法的方案即是Ans
不合法方案的环中一定会包含我们新加入的边x->y
那么假设环中剩余的路径y->x，那么形成这样的环的方案数即为，总数/(在路径上的点的入度积)，因为在路径上的点入度只能选路径上的边，其他的点仍可以随便选，
除法用逆元处理，那么我们设G[i]为所有y到i路径上的点的逆元的路的总和，按拓扑序dp一遍求出G[x]即可
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; int mo=1000000007; int du[100011],fc[100011],g[100011],next[200011],y[200011],que[200011]; int l,r,x,j,k,n,m,tx,ty,z,i,ans,tt,la; int f[100011]; void star(int i,int j) { tt++; next[tt]=g[i]; g[i]=tt; y[tt]=j; } int mi(int x,int z) { int l; l=1; while(z){ if(z%2==1)l=(ll)l*x%mo; z/=2; x=(ll)x*x%mo; } return l; } int main() { scanf("%d%d%d%d",&n,&m,&tx,&ty); for(i=1;i<=m;i++){ scanf("%d%d",&x,&z); du[z]++; star(x,z); } if(tx==ty||ty==1){ ans=1; for(i=2;i<=n;i++)ans=(ll)ans*du[i]%mo; printf("%d ",ans); } else{ ans=1; la=1; for(i=2;i<=n;i++){ la=(ll)la*du[i]%mo; if(i==ty)ans=(ll)ans*(du[i]+1)%mo; else ans=(ll)ans*du[i]%mo; fc[i]=mi(du[i],mo-2); } l=r=1; que[l]=1; while(l<=r){ x=que[l]; j=g[x]; while(j!=0){ k=y[j]; du[k]--; if(du[k]==0&&k!=ty){ r++; que[r]=k; } j=next[j]; } l++; } f[ty]=fc[ty]; l=r=1; que[l]=ty; while(l<=r){ x=que[l]; j=g[x]; while(j!=0){ k=y[j]; f[k]=((ll)f[k]+(ll)f[x]*fc[k]%mo)%mo; du[k]--; if(du[k]==0){ r++; que[r]=k; } j=next[j]; } l++; } la=(ll)la*f[tx]%mo; ans=ans-la; ans=(ans%mo+mo)%mo; printf("%d ",ans); } }