← 返回题目列表

AtCoder · mujin_pc_2017_d

D. 定向树

中文机器翻译题面 查看原题

分数: 1800 点

问题陈述

有一棵树 T 与 N 顶点,已编号 1 通过 N。 对于每个 1 ≤ i ≤ N - 1, i第一条边连接顶点 a_i 和 b_i.

Snuke 正在构建有向图 T' 通过任意指定每个边缘的方向 T。 2^{N - 1} 不同的构建方式 T'.)

对于固定 T',我们将定义 d(s,\ t) 对于每个 1 ≤ s,\ t ≤ N,如下:

  • d(s,\ t) = (从顶点移动时必须逆着指定方向遍历的边数 s 到顶点 t)

特别是, d(s,\ s) = 0 对于每个 1 ≤ s ≤ N。 另请注意,一般来说, d(s,\ t) ≠ d(t,\ s).

我们将进一步定义 D 如下:

3d2f3f88e8fa23f065c04cd175c14ebf.png

Snuke 正在构建 T' 这样 D 将是可能的最小值。 有多少种不同的构造方法 T' 这样 D 将是最小可能值,模 10^9 + 7?

约束

  • 2 ≤ N ≤ 1000
  • 1 ≤ a_i,\ b_i ≤ N
  • 给定的图是一棵树。

输入

输入由标准输入按以下格式给出:

N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}

输出

打印不同构造方式的数量 T' 这样 D 将是最小可能值,模 10^9 + 7.


示例输入 1

4
1 2
1 3
1 4

示例输出 1

2

的最小可能值 D is 1。 有两种构造方法 T' 达到这个值,如下图所示:


示例输入 2

4
1 2
2 3
3 4

示例输出 2

6

的最小可能值 D is 2。 有六种构造方法 T' 达到这个值,如下图所示:


示例输入 3

6
1 2
1 3
1 4
2 5
2 6

示例输出 3

14

示例输入 4

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

示例输出 4

102