QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
[+5]

# 5367. 递增树列

Statistics

给定一棵 n 个点的有根树,点的标号为 1n ,根的标号为 1

定义 dis(x) 为点 x 到根的最短路径的边的数量,lca(x,y)x,y 的最近公共祖先。

你需要求有几个 1n 的排列 p ,满足对于 1i<n1,有 dis(lca(pi,pi+1))dis(lca(pi+1,pi+2))

由于答案可能很大,你只需要输出答案对 1000000007 取模后的值。

输入格式

第一行一个正整数 n 表示点数。

接下来 n 行,每行两个整数 (x,y),表示树的一条边 (x,y)

输出格式

输出方案数对 1000000007 取模后的值

样例数据

样例 1 输入

3
1 2
2 3

样例 1 输出

4

样例 2 输入

5
1 2
2 3
1 4
4 5

样例 2 输出

56

子任务

对于所有的测试点,均满足 2n80;1ui,vin;uivi

  • Subtask 1(9 pts): n8
  • Subtask 2(11 pts): n15
  • Subtask 3(15 pts): n30
  • Subtask 4(25 pts): n50
  • Subtask 5(40 pts): 没有额外的限制。