QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

# 5367. 递增树列

Statistics

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

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

你需要求有几个 $1 \cdots n$ 的排列 $p$ ,满足对于 $1 \leq i < n - 1$,有 $\mathrm{dis}(\mathrm{lca}(p_i,p_{i+1})) \leq \mathrm{dis}(\mathrm{lca}(p_{i+1},p_{i+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

子任务

对于所有的测试点,均满足 $2≤n≤80;1≤u_i,v_i≤n;u_i≠v_i$。

  • Subtask 1(9 pts): $n≤8$。
  • Subtask 2(11 pts): $n≤15$。
  • Subtask 3(15 pts): $n≤30$。
  • Subtask 4(25 pts): $n≤50$。
  • Subtask 5(40 pts): 没有额外的限制。