Description
「恒逸，你相信灵魂的存在吗？」
Input
输入文件的第一行包含四个整数 n、m、x和y，依次代表枫叶上的穴位数、脉
Output
输出一行，为添加了从穴位 x连向穴位 y的脉络后，枫叶上以穴位 1 为根的脉
Sample Input
1 2
1 3
2 4
3 2
Sample Output
HINT
对于所有测试数据，1 <= n <= 100000，n - 1 <= m <= min(200000, n(n – 1) / 2)，
题解
首先我们简化这个问题，考虑一个$DAG$中树形图的个数。
值得注意的是这里有朱刘算法的一个推广：
如果除根节点外每个点都选择一条入边，由于没有环，因此一定会形成一个树形图。
这里简要证明一下：
首先证明这个图是联通的。
采用反证法，假设图不联通，显然原图存在一个子图满足：子图联通，并且子图中边数$w$>点数$u$。
那么这样这个子图的总入度>总点数。那么一定存在一个点入度>$1$。与题设不符，原命题成立。
下证这个连通图满足树形图的性质。
依旧采用反证法，我们假设选择满足题意的边不能够成树形图。那么存在两条不同的路径$S_1$，$S_2$从根节点$1$到达另外一个节点$v$。
假设子图$g(u',w') ⊂$ 原图$G(u,w)$是满足$S_1,S_2 ⊂ g(u',w')$的极小子图。
既然存在两条不同的路径，显然$u' <= w'$。
又由于除根节点外每个点有且仅有一个入边，显然$w' = u'-1$。矛盾，原命题成立。
由上述结论，显然简化版的问题答案就是：$$ans = \prod_{i=2}^n degree_i（其中degree_i表示节点i的入度）$$
我们再来考虑原问题，现在加上额外的一条边之后，原图可能形成环。再由上面的决策，显然不可行。
我们考虑不合法的情况是什么：显然选边的时候构成环就是不合法的。并且这个环中的一条边肯定是$x \rightarrow y$。
容易得到的结论就是，需要减去的不合法的值就是$$\sum_{S是G中y \rightarrow x的一条路径的点集}\prod_{2\leq j\leq n,j\notin S}degree_j$$
考虑贡献法来计算，用$top-sort-dp$，记$f_i$表示$$\sum_{S是G中y \rightarrow i的一条路径的点集}\prod_{2\leq j\leq n,j\notin S}degree_j$$
$dp$方程就是$$f_i=\frac{\sum_{j\rightarrow i}f_j}{degree_i}$$
初值$$f_y=\frac{\prod_{i=2}^ndegree_i}{degree_y}$$
由于$1$号根节点不选入边，所以$1$号点显然不能构成环。若$y == 1$，显然这条边不可能被选，不用$top-sort-dp$，直接输出原始$ans$即可。
//It is made by Awson on 2017.12.24
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
const int N = ;
const int M = ;
const int MOD = ; int n, m, x, y, u, v;
struct tt {
int to, next;
}edge[M+];
int path[N+], top;
int ans = , degree[N+], in[N+];
int f[N+];
queue<int>Q; int quick_pow(int a, int b) {
int cnt = ;
while (b) {
if (b&) cnt = (LL)cnt*a%MOD;
a = (LL)a*a%MOD;
b >>= ;
}
return cnt;
}
void topsort() {
f[y] = ans;
for (int i = ; i <= n; i++) if (in[i] == ) Q.push(i);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
f[u] = (LL)f[u]*quick_pow(degree[u], MOD-)%MOD;
for (int i = path[u]; i; i = edge[i].next) {
(f[edge[i].to] += f[u]) %= MOD; in[edge[i].to]--;
if (in[edge[i].to] == ) Q.push(edge[i].to);
}
}
}
void add(int u, int v) {
edge[++top].to = v;
edge[top].next = path[u];
path[u] = top;
}
void work() {
scanf("%d%d%d%d", &n, &m, &x, &y);
degree[y]++;
for (int i = ; i <= m; i++) {
scanf("%d%d", &u, &v);
add(u, v); degree[v]++;
}
for (int i = ; i <= n; i++) ans = (LL)ans*degree[i]%MOD;
for (int i = ; i <= n; i++) in[i] = degree[i]; in[y]--;
if (y != ) topsort();
printf("%d\n", (ans-f[x]+MOD)%MOD);
}
int main() {
work();
return ;
}