遍历计数 题解

题目分析

给定一棵有 $n$ 个结点的树，求所有可能的深度优先遍历序列的总数，答案对 $10^9$ 取模。

深度优先遍历（DFS）的过程是：先任选一个起点，之后每次优先走向未访问过的相邻结点，无路可走时回溯。过程中按照第一次访问结点的顺序记录结点编号，得到一个排列。因为起点可以任选，且每一步访问邻接点的顺序也可以任选，所以同一棵树可以产生许多不同的 DFS 序列。我们需要统计这些不同序列的数量。

解题思路

固定起点的 DFS 序列数

假设我们固定起点为 $s$，那么序列的第一个元素一定是 $s$。将树看作以 $s$ 为根的有根树：根 $s$ 有 $\deg(s)$ 个子树（即它的所有邻居），而其它任意结点 $u$（$u \neq s$）在 DFS 过程中只会从父结点进入，然后去访问它的子结点。结点 $u$ 的子结点个数等于 $\deg(u) - 1$（总度数减去父结点）。

在 DFS 过程中，每当到达一个结点，它可以以任意顺序访问它的各个子结点。因此：

• 根 $s$ 有 $\deg(s)$ 个子结点，产生的不同访问顺序有 $\deg(s)!$ 种。
• 对于其它结点 $u$，有 $(\deg(u)-1)!$ 种子结点的访问顺序。

由于各结点的子结点访问顺序相互独立，以 $s$ 为起点的 DFS 序列总数为：

所有起点的总序列数

对于不同的起点 $s$，生成的序列的第一个元素不同，因此不同起点产生的序列互不重复。所以总的 DFS 序列数就是将所有可能起点的序列数相加：

提取公因式 $\prod\limits_{u=1}^{n} (\deg(u)-1)!$，可以简化为：

由于树的边数为 $n-1$，度数之和 $\sum \deg(s) = 2(n-1)$，因此答案也可以写为：

两种形式都可以用于计算。

特殊情况

当 $n=1$ 时，唯一结点度数为 $0$，公式中的 $(\deg(u)-1)!$ 没有意义。此时显然只有 $[1]$ 这一种 DFS 序列，应直接输出 $1$。

算法说明与代码实现

参考代码采用前缀积和后缀积的方法来高效计算答案，避免了重复的乘法操作。

• 首先读入 $n$，统计每个结点的度数 deg[i]。
• 预计算阶乘数组 fac，其中 fac[i] = i! mod 1e9。
• 定义 pre[i] 表示前 $i$ 个结点的 $(\deg - 1)!$ 的乘积（前缀积）。
  即 pre[i] = pre[i-1] * fac[deg[i]-1] % mod。
• 定义 suf[i] 表示从第 $i$ 个结点到第 $n$ 个结点的 $(\deg - 1)!$ 的乘积（后缀积）。
  即 suf[i] = suf[i+1] * fac[deg[i]-1] % mod。

对于每个结点 $i$，以 $i$ 为起点的 DFS 序列数等于：

将所有 $i$ 的结果累加即得最终答案。

这种写法的时间复杂度为 $O(n)$，空间复杂度也为 $O(n)$，在 $n \le 10^5$ 时完全可以接受。由于模数 $10^9$ 不是质数，计算全程只涉及乘法与取模，无需逆元。

参考代码

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5const int N = 1e5 + 5;
6const int mod = 1e9;          // 模数 10^9
7
8int n, deg[N], fac[N];
9int pre[N], suf[N];
10int ans;
11
12int main() {
13    scanf("%d", &n);
14    
15    // 特判 n = 1
16    if (n == 1) {
17        printf("1\n");
18        return 0;
19    }
20    
21    // 预处理阶乘
22    fac[0] = 1;
23    for (int i = 1; i <= n; i++)
24        fac[i] = 1ll * fac[i - 1] * i % mod;
25    
26    // 统计度数
27    for (int i = 1; i < n; i++) {
28        int u, v;
29        scanf("%d%d", &u, &v);
30        deg[u]++;
31        deg[v]++;
32    }
33    
34    // 前缀积：pre[i] = ∏_{j=1}^{i} (deg[j]-1)!
35    pre[0] = 1;
36    for (int i = 1; i <= n; i++)
37        pre[i] = 1ll * pre[i - 1] * fac[deg[i] - 1] % mod;
38    
39    // 后缀积：suf[i] = ∏_{j=i}^{n} (deg[j]-1)!
40    suf[n + 1] = 1;
41    for (int i = n; i >= 1; i--)
42        suf[i] = 1ll * suf[i + 1] * fac[deg[i] - 1] % mod;
43    
44    // 累加每个起点的答案
45    for (int i = 1; i <= n; i++)
46        ans = (ans + 1ll * pre[i - 1] * fac[deg[i]] % mod * suf[i + 1]) % mod;
47    
48    printf("%d\n", ans);
49    return 0;
50}

代码解释

1. 度数统计
   读取 $n-1$ 条边，每一条边使两端点的度数加 1。最终得到每个结点的度数 $\deg[i]$。

2. 阶乘数组
   fac[i] 表示 $i! \bmod 10^9$，在后续计算中直接使用。

3. 前缀积 pre
pre[i] 存储了 $(\deg(1)-1)! \times (\deg(2)-1)! \times \cdots \times (\deg(i)-1)!$ 模 $10^9$ 的结果。pre[0] 初始化为 $1$。

4. 后缀积 suf
suf[i] 存储了 $(\deg(i)-1)! \times (\deg(i+1)-1)! \times \cdots \times (\deg(n)-1)!$ 模 $10^9$ 的结果。suf[n+1] 初始化为 $1$。

5. 计算答案
   对于结点 $i$，pre[i-1] 乘上 fac[deg[i]]（即 $\deg(i)!$）再乘上 suf[i+1]，就得到了以 $i$ 为起点的序列数。将所有 $i$ 的结果相加并取模即可。

6. 特判
   原参考代码未包含特判，在实际运行时遇到 $n=1$ 会因为 deg[1]-1 = -1 导致数组越界。上述代码增加了 $n=1$ 的特判，直接输出 $1$。

时间复杂度分析

• 统计度数：$O(n)$。
• 预处理阶乘：$O(n)$。
• 计算前后缀积：$O(n)$。
• 求和计算答案：$O(n)$。

总时间复杂度为 $O(n)$，空间复杂度也为 $O(n)$，满足题目要求。