#1733. 递增树列

    ID: 1733 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1085来源:qoj.ac数据:公开样例最短路径动态规划树上算法

递增树列

递增树列

题目描述

标题: 递增树列 - Problem - QOJ.ac

#5367. 递增树列

Statistics

The problem was used in the following contests:

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

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

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

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

输入格式

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

接下来 n−1 行,每行两个整数 (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≤ui,vi≤n;ui≠vi。

  • 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): 没有额外的限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
1 2
2 3
4

样例 2

5
1 2
2 3
1 4
4 5
56