: 遍历计数)
2025年6月GESP真题及题解(C++八级): 遍历计数
题目描述
给定一棵有n nn个结点的树T TT，结点依次以1 , 2 , … , n 1,2,\dots,n1,2,…,n标号。树T TT的深度优先遍历序可由以下过程得到：
- 选定深度优先遍历的起点s ss（1 ≤ s ≤ n 1 \leq s \leq n1≤s≤n），当前位置结点即是起点。
- 若当前结点存在未被遍历的相邻结点u uu则遍历u uu，也即令当前位置结点为u uu并重复这一步；否则回溯。
- 按照遍历结点的顺序依次写下结点编号，即可得到一组深度优先遍历序。
第一步中起点的选择是任意的，并且第二步中遍历相邻结点的顺序也是任意的，因此对于同一棵树T TT可能有多组不同的深度优先遍历序。请你求出树T TT有多少组不同的深度优先遍历序。由于答案可能很大，你只需要求出答案对10 9 10^9109取模之后的结果。
输入格式
第一行，一个整数n nn，表示树T TT的结点数。
接下来n − 1 n-1n−1行，每行两个正整数u i , v i u_i, v_iui,vi，表示树T TT中的一条连接结点u i , v i u_i, v_iui,vi的边。
输出格式
输出一行，一个整数，表示树T TT的不同的深度优先遍历序数量对10 9 10^9109取模的结果。
输入输出样例 1
输入 1
4 1 2 2 3 3 4输出 1
6输入输出样例 2
输入 2
8 1 2 1 3 1 4 2 5 2 6 3 7 3 8输出 2
112说明/提示
对于40 % 40\%40%的测试点，保证1 ≤ n ≤ 8 1 \leq n \leq 81≤n≤8。
对于另外20 % 20\%20%的测试点，保证给定的树是一条链。
对于所有测试点，保证1 ≤ n ≤ 10 5 1 \leq n \leq 10^51≤n≤105。
思路分析
问题理解：题目要求计算一棵树所有可能的深度优先遍历序列的数量，其中起点任意，且每个节点处访问子节点的顺序任意。
关键转化：通过分析发现，固定起点 s时，DFS序列的数量等于树以 s为根时，每个节点的子节点数的阶乘的乘积。进一步推导出总数量为：
$
S = \left(\prod_{u=1}^n (d(u)-1)!\right) \times \sum_{v=1}^n d(v)
$
其中 d(u)是节点 u的度数。算法步骤：
- 读取节点数 n，若 n=1则直接输出 1。
- 读取边并统计每个节点的度数。
- 预计算阶乘数组，便于后续直接取值。
- 计算乘积 P =∏ \prod∏(d(u)-1)!。
- 计算总度数之和（即 2(n-1)）。
- 输出P × sum_deg m o d 10 9 P \times \text{sum\_deg} \bmod 10^9P×sum_degmod109。
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintMOD=1000000000;// 取模基数intmain(){intn;scanf("%d",&n);// 特判单节点情况if(n==1){printf("1\n");return0;}vector<int>deg(n+1,0);// 度数数组，1‑based// 读入边并统计度数for(inti=0;i<n-1;++i){intu,v;scanf("%d%d",&u,&v);deg[u]++;deg[v]++;}// 预计算阶乘，最大可能需要 n-1 的阶乘vector<longlong>fact(n+1);fact[0]=1;// 0! = 1for(inti=1;i<=n;++i){fact[i]=fact[i-1]*i%MOD;}// 计算 P = ∏ (d(u)-1)!longlongP=1;for(inti=1;i<=n;++i){// 每个节点的度数至少为1，因此 deg[i]-1 >= 0P=P*fact[deg[i]-1]%MOD;}// 计算总度数之和，即 2*(n-1)longlongsum_deg=2LL*(n-1);// 最终答案 = P * sum_deg mod MODlonglongans=P*sum_deg%MOD;printf("%lld\n",ans);return0;}功能分析
1.复杂度：
时间复杂度 O(n)，空间复杂度 O(n)。
2.注意事项：
- 单独处理 n=1 的情况，避免出现负数下标。
- 使用
long long防止中间结果溢出。 - 模数为10 9 10^9109，不是质数，但只需乘法取模，不影响计算。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
