[luogu3244 HNOI2015] 落忆枫音(容斥原理+拓扑排序)

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 2

Sample Output

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<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#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 <int> V[N];
queue <int> 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;
}