← 返回题目列表

AtCoder · tdpc_tree

N. 树

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

问题陈述

从顶点 1 到顶点 N 画有图形的纸面。Snuke君决定在顶点 a_i 和边 b_i 之间画边,形成一棵树。当想在画树的过程中边始终保持连通时,求绘边顺序共有多少种,结果对 1,000,000,007 取模。

约束

  • 2 ≤ N ≤ 1000
  • 1 ≤ a_i, b_i ≤ N
  • 输入将表示一棵树。

输入格式

输入是按以下格式从标准输入给出的。
N
a_1 b_1
...
a_{N-1} b_{N-1}

输出格式

将答案输出到一行中。

示例输入 1

4
1 2
2 3
3 4

示例输出 1

4
  • 1-2 -> 2-3 -> 3-4
  • 2-3 -> 1-2 -> 3-4
  • 2-3 -> 3-4 -> 1-2
  • 3-4 -> 2-3 -> 1-2
有 4 种顺序可以考虑。(如果先写 1-2 和 3-4 的边,那么在那时边将变得非连通。)

示例输入 2

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

示例输出 2

752