GESP 题解库 / 8 级题解 / [GESP202506 八级] 遍历计数 · 第 7 / 24 题
GESP202506 八级 · P13020 · 困难

遍历计数

对每个结点数"子结点能怎么排",连乘起来,最后乘上 Σ deg = 2(n − 1)。

🌳
n ≤ 10⁵
树的结点数
🔢
模 10⁹
答案取模
⚡
O(n)
只需统计度数
🎯
Π (deg − 1)! × 2(n − 1)
核心结论
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定一棵有 n 个结点的树 T,结点依次以 1, 2, …, n 标号。树 T 的深度优先遍历序可由以下过程得到:

  1. 选定深度优先遍历的起点 s(1 ≤ s ≤ n),当前位置结点即是起点。
  2. 若当前结点存在未被遍历的相邻结点 u 则遍历 u,也即令当前位置结点为 u 并重复这一步;否则回溯。
  3. 按照遍历结点的顺序依次写下结点编号,即可得到一组深度优先遍历序。

第一步中起点的选择是任意的,并且第二步中遍历相邻结点的顺序也是任意的,因此对于同一棵树 T 可能有多组不同的深度优先遍历序。请你求出树 T 有多少组不同的深度优先遍历序。由于答案可能很大,你只需要求出答案对 10⁹ 取模之后的结果。

输入格式:第一行一个整数 n;接下来 n − 1 行,每行两个正整数 uᵢ, vᵢ,表示树中的一条边。

输出格式:一行一个整数,表示不同的深度优先遍历序数量对 10⁹ 取模的结果。

输入输出样例

样例输入输出
#14
1 2
2 3
3 4
6
#28
1 2
1 3
1 4
2 5
2 6
3 7
3 8
112

数据范围:1 ≤ n ≤ 10⁵;40% 的测试点 1 ≤ n ≤ 8,另外 20% 的测试点给定的树是一条链。

💡
人话翻译:把 DFS 的"自由选择权"数清楚。
自由选择权有两处:① 起点任选(n 种);② 站在某个结点上时,没走过的邻居按什么顺序走。
关键观察:起点不同 → 序列第一个元素不同 → 序列必然不同,所以可以按起点分类再相加,互不重叠。
固定起点 s 后,把 s 看成根:每个结点 u 的"儿子们"在它的子树块里可以任意排队——根 s 有 deg(s) 个儿子,排法是 deg(s)! 种;非根结点 u 的父结点位置已定,只剩 deg(u) − 1 个儿子,排法是 (deg(u) − 1)! 种。
于是 f(s) = deg(s)! × Πu≠s (deg(u) − 1)!。
把所有起点加起来,就是 Πu (deg(u) − 1)! × 2(n − 1)。

🔍 关键词提取

树的深度优先遍历乘法原理阶乘连乘按起点分类模 10⁹

已知条件

项目说明
输入第一行 n;随后 n − 1 行每行 uᵢ、vᵢ
输出不同深度优先遍历序的组数对 10⁹ 取模
数据范围1 ≤ n ≤ 10⁵
部分分40%:n ≤ 8;另有 20%:树是一条链
度数之和Σu deg(u) = 2(n − 1)
取模10⁹(不是质数;本题没有除法,不受影响)

需要解决的问题

02
思维导图
整理解题思路的全貌
🌳 按起点分类,数清每一层的"排列自由"
🧠 关键观察
固定 DFS 规则:没走过就走,走不动才回溯
起点不同 → 首元素不同 → 序列必不同
同一子树在序列里占连续一段
于是"按起点相加"不重不漏
🧩 单起点计数 f(s)
以 s 为根,答案 = 各结点儿子排列数之积
根 s:deg(s) 个邻居任排 → deg(s)!
非根 u:父结点已占一格 → (deg(u) − 1)!
叶子 deg = 1 → 0! = 1,无影响
➗ 求和化简
P = Π_u (deg(u) − 1)!
f(s) = deg(s)! × Π_{u≠s}(deg(u)−1)! = P × deg(s)
Σ_s f(s) = P × Σ_s deg(s)
Σ_s deg(s) = 2(n − 1) → 答案 = P × 2(n − 1)
⚠️ 易错点
n = 1 代入公式得 0,必须单独输出 1
把 Σ deg 当成 n(起点个数)
以为每个起点的方案数都一样
用 int 连乘 / 忘记取模
03
样例手算推导
样例 1、样例 2 的公式手算 + 小树暴力枚举对照

🧮 样例 1 与样例 2:公式直接算

两个样例都能"一行公式"算出来,先看这张度数表。

样例各结点度数Π (deg − 1)!2(n − 1)答案
#1(链 1–2–3–4)1, 2, 2, 10! × 1! × 1! × 0! = 166
#2(三叉 + 两组二儿子)3, 3, 3, 1, 1, 1, 1, 12! × 2! × 2! × 0!⁵ = 814112
1
样例 1:链上没有任何"选择自由"

链的度数序列是 1, 2, 2, 1

每个结点的 (deg − 1)! 都是 1(0! = 1! = 1)

只有"起点"这一处自由:Σ deg = 1 + 2 + 2 + 1 = 6

具体序列:从 1 出发走 1,2,3,4;从 2 出发可先左后右或先右后左,共 2 种;

从 3 出发同理 2 种;从 4 出发 1 种 → 1 + 2 + 2 + 1 = 6

✅ 1 × 6 = 6

2
样例 2:三个"有 3 个邻居"的结点,各贡献 (3 − 1)! = 2

deg(1) = 3(邻居 2、3、4)→ 因子 (3 − 1)! = 2

deg(2) = 3(父 1 加儿子 5、6)→ 因子 (3 − 1)! = 2

deg(3) = 3(父 1 加儿子 7、8)→ 因子 (3 − 1)! = 2

deg(4) = deg(5) = deg(6) = deg(7) = deg(8) = 1 → 因子 0! = 1

P = 2 × 2 × 2 × 1⁵ = 8;Σ deg = 3 + 3 + 3 + 1 × 5 = 14

答案 = 8 × 14 = 112

✅ 8 × 14 = 112

3
再把"起点之和"对上

Σ_s deg(s) = 3 + 3 + 3 + 1 + 1 + 1 + 1 + 1 = 14 = 2 × (8 − 1)

也就是"以 1 为起点"贡献 P × 3 = 24

"以叶子 4 为起点"只贡献 P × 1 = 8

把 8 个起点的贡献加起来:3 个度为 3 的结点各 24

5 个叶子各 8 → 24 × 3 + 8 × 5 = 72 + 40 = 112

✅ 112 = 8 × 14

🔑
公式为什么好记:把"起点自由"和"儿子排序自由"分开看——
· 儿子排序自由:每个结点贡献一个 (deg(u) − 1)!,乘起来得 P;
· 起点自由:根比其他结点多一个"能从哪个方向进来"的选择,刚好把 (deg(s) − 1)! 升级成 deg(s)! = (deg(s) − 1)! × deg(s),多出来的因子就是 deg(s)。
把 deg(s) 对全部起点求和,就用上了树的恒等式 Σ deg = 2(n − 1)。

🔎 小树实验:5 结点菊花,亲手把公式验到底

拿 5 个结点的菊花(中心 1,叶子 2、3、4、5)做实验:度数序列是 4, 1, 1, 1, 1,于是 P = (4 − 1)! × 0!⁴ = 6,Σ deg = 4 + 1 × 4 = 8 = 2(n − 1),公式给出 6 × 8 = 48。下面把 48 种逐一归类点清。

起点 s以 s 为根后的树形状枚举出的序列长什么样个数f(s) = P × deg(s)
1(中心,deg = 4)根 1 带四个儿子 2、3、4、51 打头,后接 2、3、4、5 的任意排列:1,2,3,4,5 / 1,2,3,5,4 / 1,2,4,3,5 / …(共 4! 种)246 × 4 = 24
2(叶子,deg = 1)根 2 带一个儿子 1;1 再带儿子 3、4、52,1 打头,后接 3、4、5 的任意排列:2,1,3,4,5 / 2,1,3,5,4 / 2,1,4,3,5 / …(共 3! 种)66 × 1 = 6
3(叶子,deg = 1)同上(把 3 换到"根"的位置)3,1 打头,后接 2、4、5 的排列66 × 1 = 6
4(叶子,deg = 1)同上4,1 打头,后接 2、3、5 的排列66 × 1 = 6
5(叶子,deg = 1)同上5,1 打头,后接 2、3、4 的排列66 × 1 = 6
1
为什么"叶子起点"反而能给出 3! = 6 种?

叶子 2 只有 1 个邻居(结点 1),第一步没得选:2 → 1

但到了 1 之后,它没走过的邻居有 3、4、5 三个 → 3! = 6 种排法

所以"以 2 为起点"共有 6 个序列

换成公式看:以 2 为根时,1 变成非根结点,

它原来度数是 4,作为非根只剩 deg(1) − 1 = 3 个儿子 → 3! = 6 ✓

叶子 3、4、5 的度数是 1 → 0! = 1,不再贡献任何因子

✅ f(2) = 1! × (4 − 1)! × 1 × 1 × 1 = 1 × 6 = 6

2
为什么"中心起点"有 4! = 24 种?

以 1 为根时,1 的四个邻居 2、3、4、5 全是儿子,可以任意排队

排法 4! = 24 种;每棵子树只有一个结点,内部没有额外的自由

所以"以 1 为起点"共 24 个序列

换成公式看:deg(1)! × Π_{u≠1}(deg(u) − 1)! = 4! × 1⁴ = 24 ✓

而 P × deg(1) = 6 × 4 = 24,两种写法一致

✅ f(1) = 24

3
总数核对

24(中心起点) + 6 × 4(四片叶子起点) = 24 + 24 = 48

公式:P × 2(n − 1) = 6 × 8 = 48 ✓

如果把"起点自由"错当成"每个起点的方案数都一样",

就会算成 24 × 5 = 120 或 6 × 5 = 30,两个都不对

✅ 48 = 6 × 8,全部对上

⚠️
这里最容易翻车的两点:① P = Πu (deg(u) − 1)! 用的是原树度数;换任何结点当根,结点 u 的因子都还是 (deg(u) − 1)!(父结点只占掉 1 格),所以 P 与根的选择无关,是真正的公因子;② "起点自由"带来的额外因子恰好是 deg(s),它不是一个常数,因此必须对全部起点求和(用 Σ deg = 2(n − 1)),绝不能简单地乘 n。
04
解法对比
乘法原理连乘 vs 只算一个起点再乘 n vs 暴力枚举

⚔️ 解法对比

🟢 阶乘连乘 + 度数和(推荐) 推荐

答案 = Πu (deg(u) − 1)! × 2(n − 1),一次遍历统计度数即可

  • 时间 O(n)
  • 只需一个度数数组
  • 代码约 15 行
  • 把"起点自由"化成常数 2(n − 1)
💡
正确性来源:① 起点不同 ⇒ 序列首元素不同 ⇒ 不同起点的序列集互不相交;② 固定起点后,每个结点的"儿子排列"互相独立 ⇒ 乘法原理;③ Σs deg(s) = 2(n − 1) 是树的度数恒等式。
三条凑起来,答案必然等于 P × 2(n − 1)。

🟠 只算一个起点、再乘 n

以为每个起点的方案数都是 deg(1)! × Π(deg − 1)!,直接乘 n

  • 时间 O(n)
  • 写法看起来更简单
  • 但结论是错的
  • 菊花树上立刻露馅
⚠️
为什么错:不同起点的方案数并不相同——它等于 P × deg(s),与起点的度数成正比。
以 5 结点菊花为例(P = 6):中心为起点有 24 种,叶子为起点只有 6 种;
正确答案 48,而"乘 n"会给出 24 × 5 = 120,错得离谱。

📈 性能对比

方案复杂度结论
阶乘连乘 + 度数和O(n)✅ 正解,代码最短
只算一个起点再乘 nO(n)❌ 错:f(s) 与 deg(s) 成正比,不是常数
暴力枚举所有遍历序结点数阶乘级❌ 连 n = 8 都很勉强,只能骗 40% 部分分
05
算法流程图
统计度数 → 连乘阶乘 → 乘 2(n − 1)
开始读入 nn 等于 1 吗?是 ✓输出 1否 ✗继续统计度数读入 n − 1 条边,统计 deg(u)P = 1枚举每个结点 u把 (deg(u) − 1)! 乘进 P,并对 10⁹ 取模所有结点都乘过了吗?ans = P × 2(n − 1) 再对 10⁹ 取模输出 ans换下一个结点 u
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌳 遍历序数量计算器(公式 + 暴力交叉验证)

第一行输入 n,随后 n − 1 行输入一条边的两个端点。程序用公式算出答案,并在 n ≤ 7 时旁路跑一次暴力枚举做交叉验证。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(度数 + 阶乘连乘)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1000000000LL;      // 10^9(本题只有乘法,模数是不是质数无所谓)

int main() {
    int n;
    scanf("%d", &n);
    if (n == 1) { puts("1"); return 0; }   // 单结点:唯一的遍历序就是 [1]

    vector<int> deg(n + 1, 0);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        deg[u]++; deg[v]++;
    }

    // P = Π_u (deg(u) − 1)!   (边算边取模)
    ll P = 1;
    for (int u = 1; u <= n; u++) {
        for (int k = 2; k <= deg[u] - 1; k++)
            P = P * k % MOD;
    }

    // 答案 = P × Σ_s deg(s) = P × 2(n − 1)
    ll ans = P * (2LL * (n - 1) % MOD) % MOD;
    printf("%lld\n", ans);
    return 0;
}
🔑
为什么这段短短十几行是对的:内层循环把 (deg(u) − 1)! 的每一个因子乘进 P,因为乘法满足结合律,"对每个 u 分别求阶乘再相乘"与"把全部因子乘到一起"完全等价。
所有结点的因子个数之和 = Σu (deg(u) − 1) = Σ deg − n = 2(n − 1) − n = n − 2,所以总乘法次数不超过 n,整体 O(n)。

📖 关键几行怎么看

代码作用为什么这样写
if (n == 1) { puts("1"); return 0; }特判边界n = 1 时 2(n − 1) = 0,公式会输出 0,必须单独处理
deg[u]++; deg[v]++;统计度数无向边对两端的度数都有贡献
for (int k = 2; k <= deg[u] - 1; k++)连乘阶乘(deg − 1)! 就是 2 × 3 × … × (deg − 1);deg ≤ 2 时循环不执行,因子为 1
P = P * k % MOD;边算边取模阶乘会瞬间超过 long long,必须随时取模
2LL * (n - 1) % MOD度数和Σ_s deg(s) = 2(n − 1),把 n 个起点一次算完
⚠️
五个坑:① n = 1 没特判(答案错成 0);② 把 Σs deg(s) 写成 n(起点个数不等于度数和);③ 误以为"每个起点的方案数相同"(应该是 P × deg(s));④ 忘记 0! = 1,把叶子因子当成 0 乘进去;⑤ 用 int 存 P 的中间乘积(10⁹ × 10⁹ 会溢出)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4
1 2
2 3
3 4
6题面样例 1(链,只有起点自由)
8
1 2
1 3
1 4
2 5
2 6
3 7
3 8
112题面样例 2(P = 8,Σ deg = 14)
11只有 1 个结点:唯一序列 [1],必须特判
2
1 2
2两个结点:1,2 与 2,1 两种
5
1 2
1 3
1 4
1 5
48菊花:中心贡献 (4 − 1)! = 6,Σ deg = 8 → 6 × 8 = 48
5
1 2
2 3
3 4
4 5
8长链:所有阶乘因子都是 1,答案就是 2(n − 1) = 8
6
1 2
1 3
1 4
1 5
5 6
60混合形状:P = 3! × 1! = 6,Σ deg = 10 → 6 × 10 = 60
✅
自查清单:① n = 1 特判了吗?② 因子用的是 (deg(u) − 1)! 吗?③ 最后乘的是 2(n − 1) 而不是 n 吗?④ 连乘过程中取模了吗?

🚨 易错点清单

⚠️
n = 1 未特判:2(n − 1) = 0 会让公式输出 0,但正确答案是 1。
⚠️
把度数和写成 n:起点个数是 n,但 Σs deg(s) = 2(n − 1),两者只在完全图式的巧合下才接近。
⚠️
以为 f(s) 是常数:不同起点的方案数是 P × deg(s),度数不同的起点贡献不一样(样例 2 里中心贡献 24、叶子只贡献 8)。
⚠️
阶乘因子算错位:非根是 (deg − 1)!,根是 deg!;两者只差一个因子 deg,别把根的因子也写成 (deg − 1)!。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
乘法次数
≤ n − 2 次
单次乘法
两数均 < 10⁹,long long 安全

时间怎么算的?

空间都用在哪?

只需要一个长度为 n + 1 的度数数组;若用"边表 + 度数"的写法,连邻接表都不用建。

✅ 复杂度低到几乎没有门槛,本题的难点全在"推导结论"而不是"跑得快"——能否想到"按起点分类 + 乘法原理 + 度数求和"才是拿分关键。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「树上按局部自由度做乘法原理计数」通用模板
// 1) 固定起点 s,把 s 当根
// 2) 每个结点 u 的"儿子们"是互相独立的排列 → 贡献 (deg_root(u))!
// 3) 起点 s 的因子要单独升级:s 的全部邻居都能排 → deg(s)!
//    非根 u 的因子是 (deg(u) − 1)!(父结点占掉一格)
// 4) 求和时提公因子 P = Π_u (deg(u) − 1)!
//    Σ_s f(s) = P × Σ_s deg(s) = P × 2(n − 1)     ← 树上度数和恒等式

ll P = 1;
for (int u = 1; u <= n; u++)
    for (int k = 2; k <= deg[u] - 1; k++)     // (deg(u) − 1)!
        P = P * k % MOD;
ll ans = P * (2LL * (n - 1) % MOD) % MOD;      // n >= 2
// n == 1 时 ans = 1(公式会算出 0,必须特判)

// 类似的"树上局部排列数相乘"可以迁移到:
//   · 树的拓扑序计数(每个子树内子结点任意排)
//   · 有根树的"子结点访问顺序"方案数
//   · 树上随机游走 / 概率题里对每个点单独算贡献再相加

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
树的度数和恒等式Σ deg = 2(n − 1) 把"逐点求和"化成常数所有"树上度数/边数/点数"互相换算的计数题
乘法原理(局部独立)各结点的儿子排列互相独立,因子直接相乘树形 DP 计数、拓扑序计数、排列组合计数
按起点分类起点不同 ⇒ 首元素不同 ⇒ 序列集不交计数时"先按某个关键量分类,再逐类求和"的通用套路
阶乘 + 取模(deg − 1)! 边乘边取模任何"排列数 / 组合数取模"的题目(无除法时模数无要求)
🌟
思考题:如果把题目改成"起点固定为 1",答案是多少?(提示:这时只剩一个起点,答案就是 f(1) = deg(1)! × Πu≠1 (deg(u) − 1)! = P × deg(1),不用再乘 2(n − 1)。
再进一步:如果要求"序列首尾相接、循环同构视为同一个"呢?那就得仔细想清楚"不同起点的序列是否可能循环同构"——把"起点"从自由变量变成约束,是这类计数题最常做的变形。)