对每个结点数"子结点能怎么排",连乘起来,最后乘上 Σ deg = 2(n − 1)。
给定一棵有 n 个结点的树 T,结点依次以 1, 2, …, n 标号。树 T 的深度优先遍历序可由以下过程得到:
s(1 ≤ s ≤ n),当前位置结点即是起点。u 则遍历 u,也即令当前位置结点为 u 并重复这一步;否则回溯。第一步中起点的选择是任意的,并且第二步中遍历相邻结点的顺序也是任意的,因此对于同一棵树 T 可能有多组不同的深度优先遍历序。请你求出树 T 有多少组不同的深度优先遍历序。由于答案可能很大,你只需要求出答案对 10⁹ 取模之后的结果。
输入格式:第一行一个整数 n;接下来 n − 1 行,每行两个正整数 uᵢ, vᵢ,表示树中的一条边。
输出格式:一行一个整数,表示不同的深度优先遍历序数量对 10⁹ 取模的结果。
输入输出样例
| 样例 | 输入 | 输出 |
|---|---|---|
| #1 | 4 | 6 |
| #2 | 8 | 112 |
数据范围:1 ≤ n ≤ 10⁵;40% 的测试点 1 ≤ n ≤ 8,另外 20% 的测试点给定的树是一条链。
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⁹(不是质数;本题没有除法,不受影响) |
deg(s)!、非根是 (deg(u) − 1)!?根没有父结点,"第一个进来的方向"也是自由选择,所以全部 deg(s) 个邻居都能任意排;非根结点是被父结点"走"过来的,父结点占掉了 deg(u) 个邻居中的 1 个,只剩 deg(u) − 1 个儿子可以任意排deg = 1,因子是 0! = 1,相当于"没有选择",乘 1 不影响答案Σs f(s) 化简成常数?提出公因子 P = Πu (deg(u) − 1)! 后 f(s) = P × deg(s),而 Σs deg(s) = 2(n − 1) 是树的恒等式两个样例都能"一行公式"算出来,先看这张度数表。
| 样例 | 各结点度数 | Π (deg − 1)! | 2(n − 1) | 答案 |
|---|---|---|---|---|
| #1(链 1–2–3–4) | 1, 2, 2, 1 | 0! × 1! × 1! × 0! = 1 | 6 | 6 |
| #2(三叉 + 两组二儿子) | 3, 3, 3, 1, 1, 1, 1, 1 | 2! × 2! × 2! × 0!⁵ = 8 | 14 | 112 |
链的度数序列是 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
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
Σ_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 个结点的菊花(中心 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、5 | 1 打头,后接 2、3、4、5 的任意排列:1,2,3,4,5 / 1,2,3,5,4 / 1,2,4,3,5 / …(共 4! 种) | 24 | 6 × 4 = 24 |
| 2(叶子,deg = 1) | 根 2 带一个儿子 1;1 再带儿子 3、4、5 | 2,1 打头,后接 3、4、5 的任意排列:2,1,3,4,5 / 2,1,3,5,4 / 2,1,4,3,5 / …(共 3! 种) | 6 | 6 × 1 = 6 |
| 3(叶子,deg = 1) | 同上(把 3 换到"根"的位置) | 3,1 打头,后接 2、4、5 的排列 | 6 | 6 × 1 = 6 |
| 4(叶子,deg = 1) | 同上 | 4,1 打头,后接 2、3、5 的排列 | 6 | 6 × 1 = 6 |
| 5(叶子,deg = 1) | 同上 | 5,1 打头,后接 2、3、4 的排列 | 6 | 6 × 1 = 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
以 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
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。答案 = Πu (deg(u) − 1)! × 2(n − 1),一次遍历统计度数即可
2(n − 1)Σs deg(s) = 2(n − 1) 是树的度数恒等式。P × 2(n − 1)。以为每个起点的方案数都是 deg(1)! × Π(deg − 1)!,直接乘 n
P × deg(s),与起点的度数成正比。| 方案 | 复杂度 | 结论 |
|---|---|---|
| 阶乘连乘 + 度数和 | O(n) | ✅ 正解,代码最短 |
| 只算一个起点再乘 n | O(n) | ❌ 错:f(s) 与 deg(s) 成正比,不是常数 |
| 暴力枚举所有遍历序 | 结点数阶乘级 | ❌ 连 n = 8 都很勉强,只能骗 40% 部分分 |
第一行输入 n,随后 n − 1 行输入一条边的两个端点。程序用公式算出答案,并在 n ≤ 7 时旁路跑一次暴力枚举做交叉验证。
点按钮开始 →
#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⁹ 会溢出)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 6 | 题面样例 1(链,只有起点自由) |
8 | 112 | 题面样例 2(P = 8,Σ deg = 14) |
1 | 1 | 只有 1 个结点:唯一序列 [1],必须特判 |
2 | 2 | 两个结点:1,2 与 2,1 两种 |
5 | 48 | 菊花:中心贡献 (4 − 1)! = 6,Σ deg = 8 → 6 × 8 = 48 |
5 | 8 | 长链:所有阶乘因子都是 1,答案就是 2(n − 1) = 8 |
6 | 60 | 混合形状:P = 3! × 1! = 6,Σ deg = 10 → 6 × 10 = 60 |
n = 1 特判了吗?② 因子用的是 (deg(u) − 1)! 吗?③ 最后乘的是 2(n − 1) 而不是 n 吗?④ 连乘过程中取模了吗?2(n − 1) = 0 会让公式输出 0,但正确答案是 1。Σs deg(s) = 2(n − 1),两者只在完全图式的巧合下才接近。P × deg(s),度数不同的起点贡献不一样(样例 2 里中心贡献 24、叶子只贡献 8)。(deg − 1)!,根是 deg!;两者只差一个因子 deg,别把根的因子也写成 (deg − 1)!。Σu (deg(u) − 1) = 2(n − 1) − n = n − 2只需要一个长度为 n + 1 的度数数组;若用"边表 + 度数"的写法,连邻接表都不用建。
✅ 复杂度低到几乎没有门槛,本题的难点全在"推导结论"而不是"跑得快"——能否想到"按起点分类 + 乘法原理 + 度数求和"才是拿分关键。
// 「树上按局部自由度做乘法原理计数」通用模板 // 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)! 边乘边取模 | 任何"排列数 / 组合数取模"的题目(无除法时模数无要求) |
f(1) = deg(1)! × Πu≠1 (deg(u) − 1)! = P × deg(1),不用再乘 2(n − 1)。