#G1122. [GESP202506 八级] 遍历计数

[GESP202506 八级] 遍历计数

[GESP202506 八级] 遍历计数

时间限制:1.0 s 内存限制:512.0 MB

题目描述

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

  1. 选定深度优先遍历的起点(1≤s≤n1\le s\le n),当前所在结点即是起点。
  2. 若当前结点存在未被遍历的相邻结点 vv,则遍历 vv,也即令当前所在结点为 vv 并重复这一步;否则回溯。
  3. 按照遍历结点的顺序依次写下结点编号,即可得到一组深度优先遍历序。

第一步中起点的选择是任意的,并且第二步中遍历相邻结点的顺序是任意的,因此对于同一棵树 GG 可能有多组不同的深度优先遍历序。请你求出树 GG 有多少组不同的深度优先遍历序。由于答案可能很大,你只需要求出答案对 10910^9 取模之后的结果。

输入格式

第一行,一个整数 nn,表示树 GG 的结点数。

接下来 n−1n-1 行,每行两个正整数 u,vu,v,表示树 GG 中的一条连接结点 u,vu,v 的边。

输出格式

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

样例 #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 1≤n≤81\le n\le 8 无
5~6 树是一条链
全部 1≤n≤1051\le n\le 10^5