德阳市网站建设_网站建设公司_MongoDB_seo优化

2025年6月GESP真题及题解(C++八级): 遍历计数

题目描述

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

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

第一步中起点的选择是任意的，并且第二步中遍历相邻结点的顺序也是任意的，因此对于同一棵树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。

思路分析

1. 问题理解：题目要求计算一棵树所有可能的深度优先遍历序列的数量，其中起点任意，且每个节点处访问子节点的顺序任意。

2. 关键转化：通过分析发现，固定起点 s时，DFS序列的数量等于树以 s为根时，每个节点的子节点数的阶乘的乘积。进一步推导出总数量为：
   $
   S = \left(\prod_{u=1}^n (d(u)-1)!\right) \times \sum_{v=1}^n d(v)
   $
   其中 d(u)是节点 u的度数。

3. 算法步骤：

   • 读取节点数 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;}