#G1122. [GESP202506 八级] 遍历计数
[GESP202506 八级] 遍历计数
[GESP202506 八级] 遍历计数
时间限制:1.0 s 内存限制:512.0 MB
题目描述
给定一棵有 个结点的树 ,结点依次以 标号。树 的深度优先遍历序可由以下过程得到:
- 选定深度优先遍历的起点(),当前所在结点即是起点。
- 若当前结点存在未被遍历的相邻结点 ,则遍历 ,也即令当前所在结点为 并重复这一步;否则回溯。
- 按照遍历结点的顺序依次写下结点编号,即可得到一组深度优先遍历序。
第一步中起点的选择是任意的,并且第二步中遍历相邻结点的顺序是任意的,因此对于同一棵树 可能有多组不同的深度优先遍历序。请你求出树 有多少组不同的深度优先遍历序。由于答案可能很大,你只需要求出答案对 取模之后的结果。
输入格式
第一行,一个整数 ,表示树 的结点数。
接下来 行,每行两个正整数 ,表示树 中的一条连接结点 的边。
输出格式
输出一行,一个整数,表示树 的不同的深度优先遍历序数量对 取模的结果。
样例 #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
数据范围
| 测试点 | 数据范围 | 说明 |
|---|---|---|
| 1~4 | 无 | |
| 5~6 | 树是一条链 | |
| 全部 |