「HNOI 2015」落忆枫音

题目大意：给定一张有向无环图，现在要求加入一条边，求加入后以 $1$ 为根的树形图个数。$n \leq 10^5$

如果除根节点外每个点都选择一条入边，由于没有环，因此一定会形成一个树形图，因此答案就是

$$\prod\limits_{i=2}^{n}dgr[i]$$

其中 $dgr[i]$ 表示第 $i$ 个点的入度。

现在加入这条边之后，我们仍然可以套用这个公式，但是这样就会有一些不合法的方案被统计进来，我们需要把这些不合法的方案减掉。

一个方案如果不合法，那么一定会形成一个环，而环一定包含新加入的那条边。

因此拓扑排序，减掉 $y$ 走到 $x$ 的状态数即可。注意特判 $y=1$ 的情况。

#include <cstdio>

const int N = 100005, P = 1e9 + 7;
int head[N], nxt[N<<1], v[N<<1], tot, dgr[N], tmp[N], res = 1, ans = 1, f[N], q[N], h = 1, t, inv[N];

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
void add_edge(int from, int to) {
    nxt[++tot] = head[from];
    head[from] = tot, v[tot] = to;
}
void previous(int n) {
    inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = 1LL * (P - P / i) * inv[P % i] % P;
}

int main() {
    int n = read(), m = read(), x = read(), y = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        add_edge(u, v), ++dgr[v], ++tmp[v];
    }
    for (int i = 2; i <= n; ++i) {
        res = 1LL * res * dgr[i] % P;
        if (i != y) ans = 1LL * ans * dgr[i] % P;
        else ans = 1LL * ans * (dgr[i] + 1) % P;
    }
    if (y == 1) { printf("%d\n", ans); return 0; }
    for (int i = 1; i <= n; ++i) if (!dgr[i]) q[++t] = i;
    f[y] = 1, previous(n);
    while (h <= t) {
        int u = q[h++];
        f[u] = 1LL * f[u] * inv[dgr[u]] % P;
        for (int i = head[u]; i; i = nxt[i]) {
            f[v[i]] = (f[v[i]] + f[u]) % P;
            if (--tmp[v[i]] == 0) q[++t] = v[i];
        }
    }
    ans -= 1LL * res * f[x] % P;
    printf("%d\n", ans < 0 ? ans + P : ans);
    return 0;
}

时间复杂度 $O(n+m)$