问题分析

给定一个有向无环图（DAG），以节点 $1$ 为根，求其生成树（脉络树）的数量。然后考虑添加一条新边 $(x, y)$ 后，新图的生成树数量。

关键数学原理

1. 有向生成树计数（Matrix-Tree 定理）

对于有向图以 $r$ 为根的生成树数量，有：

$$\text{答案} = \prod_{i=2}^n \text{deg}^{in}(i)$$

其中 $\text{deg}^{in}(i)$ 是节点 $i$ 的入度（不考虑根节点 $1$）。

2. 添加新边的影响

添加边 $(x, y)$ 后，可能会形成环。需要减去包含新边且形成环的非法方案数。

算法思路

1. 基础情况计算

int ans = 1;
for (int i = 2; i <= n; ++i)
    ans = ans * d[i] % mod;

计算原始图的生成树数量：$\text{ans} = \prod_{i=2}^n d[i]$，其中 $d[i]$ 是节点 $i$ 的入度。

2. 特殊情况处理

if (y == 1) {
    cout << ans << "\n";
    return 0;
}

如果新边指向根节点 $1$，不会影响结果，直接输出原答案。

3. 非法方案计算

使用动态规划计算包含新边的非法方案：

vis[x] = 1;
dp[x] = ans * qpow(d[x], mod - 2) % mod;
dfs(1);

定义 $dp[u]$：从 $x$ 到 $u$ 的路径对非法方案的贡献。

状态转移：

$$dp[u] = \frac{\sum_{v \in \text{children}(u)} dp[v]}{d[u]} $$

初始条件：

$$dp[x] = \frac{\text{ans}}{d[x]}$$

4. 最终答案

cout << norm(ans, dp[y]) << "\n";

最终答案 = 总方案数 - 非法方案数：

$$\text{答案} = \text{ans} - dp[y]$$

正确性证明

1. 基础公式

根据有向图 Matrix-Tree 定理，以 $1$ 为根的生成树数量为：

$$T = \prod_{i=2}^n \text{indeg}(i)$$

2. 添加新边的影响

添加边 $(x, y)$ 后，非法方案是那些包含边 $(x, y)$ 且形成环的方案。这些方案对应于：

• 在原始生成树中，从 $y$ 到 $x$ 的路径
• 加上新边 $(x, y)$ 形成环

$dp[y]$ 正好计算了这类方案的数量。

复杂度分析

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

图遍历：$O(n + m)$

动态规划：$O(n + m)$

空间复杂度：$O(n + m)$

样例解析

输入：

4 4 4 3
1 2
1 3
2 4
3 2

处理过程：

1.计算各节点入度：$d[1]=0, d[2]=2, d[3]=1, d[4]=1$

2.基础答案：$\text{ans} = d[2] \times d[3] \times d[4] = 2 \times 1 \times 1 = 2$

3.计算非法方案：$dp$ 数组计算

4.最终答案：$2 - dp[3] = 3$（具体计算过程涉及图的拓扑结构）

输出：3

关键技巧

1.模运算处理：使用模逆元处理除法

inline int qpow(int a, int b) {
    // 快速幂求逆元
}

2.记忆化搜索：避免重复计算

bitset<N> vis;  // 记录访问状态

3.拓扑顺序处理：利用DAG性质保证计算顺序正确

总结

本题通过组合数学和动态规划的结合，高效解决了有向图生成树计数问题：

1.利用 Matrix-Tree 定理计算基础生成树数量

2.通过动态规划计算添加新边后的非法方案

3.使用模运算处理大数计算

算法在 $O(n + m)$ 时间内解决问题，适用于 $n \leq 10^5$ 的大规模数据。