题目描述

给定一棵 $n$ 个结点的树 $T$。深度优先遍历可以任意选择起点，且遍历相邻结点的顺序任意，因此同一棵树可能产生多组不同的深度优先遍历序。求树 $T$ 有多少组不同的深度优先遍历序，答案对 $10^9$ 取模。

输入格式

第一行输入一个整数 $n$。 接下来 $n-1$ 行，每行输入两个正整数 $u_i,v_i$，表示一条边。

输出格式

输出一行一个整数，表示不同深度优先遍历序数量对 $10^9$ 取模的结果。

4
1 2
1 3
3 4

6

8
1 2
1 3
1 4
2 5
2 6
3 7
3 8

112

数据范围与提示

• 对于 $40$ 的测试点，保证 $1 \le n\le 8$。
• 对于另外 $20$ 的测试点，保证给定的树是一条链。
• 对于全部测试点，保证 $1 \le n\le 10^5$。
• 样例 1 为根据题意和原错位片段重建的有效样例。

来源

GESP 2025 年 06 月 C++ 八级 T2