统计树的所有可能深度优先遍历序数量
时间限制：1.0 s 内存限制：512.0 MB
题目描述
给定一棵有n个结点的树T，结点依次以1,2,…,n标号。树T的深度优先遍历序可由以下过程得到：
- 选定深度优先遍历的起点s（1≤s≤n），当前所在结点即是起点。
- 若当前结点存在未被遍历的相邻结点u则遍历，也即令当前所在结点为u并重复这一步；否则回溯。
- 按照遍历结点的顺序依次写下结点编号，即可得到一组深度优先遍历序。
由于起点的选择是任意的，且相邻结点的遍历顺序是任意的，同一棵树T可能有多组不同的深度优先遍历序。请你求出树T有多少组不同的深度优先遍历序，结果对10^9取模。
输入格式
第一行一个整数n，表示树T的结点数。 接下来n-1行，每行两个正整数u_i, v_i，表示树T中连接结点u_i和v_i的边。
输出格式
输出一行一个整数，表示树T的不同深度优先遍历序数量对10^9取模的结果。
样例
样例1
输入：
4
1 2
2 3
3 4输出：
6样例2
输入：
8
1 2
1 3
1 4
2 5
2 6
3 7
3 8输出：
112数据范围
- 对于40%的测试点，保证1≤n≤8
- 对于另外20%的测试点，保证给定的树是一条链
- 对于所有测试点，保证1≤n≤10^5
本题为编程题，提交代码并运行通过测试点后判分。
正在加载题目数据…
子题
该题型需在试卷/作业中作答，单题练习暂不支持
答案解析
提交记录
共 条
仅展示自由练习提交
正在加载提交记录…
状态
得分率
提交时间
平均用时
平均内存
使用语言
提交人
加载失败
暂无自由练习提交记录