← 返回题目列表

AtCoder · summerfes2018_g

G. 屋台冲突 (小吃摊碰撞)

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

配点 : 150 点

問題文

夏日祭 N 从鸟居到神社参拜殿的小吃摊长度 他们沿着 2N 路排列。 这条路是 从鸟居开始算起,等间隔地分为 2N 段。 k 分区 它被称为 k 。另外, i 第档 它被称为 i 。

由于每个摊位都提前获得神社的营业许可才能开店,今年所有摊位都被 2 现在您可以使用一个分区。 具体来说就是小吃摊 i 有一个分区 A_{i} 和分区 已授予使用 B_{i} 的许可。 整数A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N} 都是不同的,而且都是 i 关于 A_{i} \lt B_{i} 成立。 小吃摊 i 是神社获得营业执照的区域。 在 A_{i} 和 按字典顺序比较 B_{i} 之间来回时, 所有满足 A_{i} \leq p \leq B_{i} 的整数 p ,分区 您需要暂时通过 p 。 这样的划分 p 它存在于 i 路径上。

屋台 x 和大排档 关于 y ,如果两个小吃摊的路径上都存在路段,则生意可能会出现问题。 因此,为了了解摊位之间的关系,神社 x \neq y 大排档一组 对于 x, y ,如果两个停顿的路径上都存在一段,则顶点 连接 x 和 边缘 y 和无向边的顶点数 我创建了一个 N 的图表。 鸭嘴兽君为了充分享受夏日祭典,通过秘密途径得到了这张图,但令人惊讶的是,这张图是一棵相连的无向树。 因此,从这棵树开始,原来 我想恢复 A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N} 。

从这棵树中,原始整数集 编写一个程序来回答 (A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N}) 有多少种可能的情况。 然而,答案可能非常大,所以 打印除以 1000000007 后的余数。

制約

所有测试用例都满足以下约束。

  • 2 \leq N \leq 200000
  • 1 \leq u_{i},v_{i} \leq N (1 \leq i \leq N-1)
  • 给定的图是一个连通的无向树。

入力

输入是按以下格式从标准输入给出的。

N
u_{1} v_{1}
u_{2} v_{2}
:
u_{N-1} v_{N-1}
  • 第一行是一个整数 写入 N 。这表示鸭嘴兽获得的图的顶点数。
  • 继续 N-1 行 i 行有两个整数 u_{i} 和 按字典顺序比较 v_{i} 用空格分隔。这是图表 这表明 i 第一条边是顶点 u_{i} 和 按字典顺序比较 v_{i} 已连接。

出力

在标准输出上创建与给定图表相同的图表。 (A_{1}, A_{2}, ..., A_{N}, B_{1}, B_{2}, ..., B_{N}) 有多少种存在方式? 在一行中输出除以 1000000007 后的余数。 然而,由于鸭嘴兽君的误会等原因。 0 请注意,也可能存在输入案例。


入力例 1

3
1 2
1 3

出力例 1

8

在这种情况下,有可能 (A_{1}, A_{2}, A_{3}, B_{1}, B_{2}, B_{3}) 如下 8 方法有很多。

(A_{1}, A_{2}, A_{3}, B_{1}, B_{2}, B_{3}) =
(1,2,4,5,3,6)
(1,2,4,6,3,5)
(1,4,2,5,6,3)
(1,4,2,6,5,3)
(2,1,4,5,3,6)
(2,1,4,6,3,5)
(2,4,1,5,6,3)
(2,4,1,6,5,3)

全部 i 关于 A_{i} \lt B_{i} 。


入力例 2

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

出力例 2

0

您可以创建这样的图表 由于 (A_{1}, A_{2}, ..., A_{7}, B_{1}, B_{2}, ..., B_{7}) 不存在,因此所需的答案为 0。