分数: 900 点
问题陈述
让 N 是偶数。
有一棵树 N 顶点。 顶点已编号 1, 2, ..., N。 对于每个 i (1 \leq i \leq N - 1), i第一条边连接顶点 x_i 和 y_i.
Snuke 想用丝带装饰树,如下所示。
首先,他将划分 N 顶点变成 N / 2 对。 这里,每个顶点必须恰好属于一对。 然后,对于每一对 (u, v),将丝带穿过之间的最短路径中包含的所有边 u 和 v.
Snuke 尝试将顶点分成两对,以满足以下条件:“对于每条边,至少有一条带穿过它。” 有多少种方法可以将顶点分成对,满足这个条件? 求计数模数 10^9 + 7。 这里,当存在一个对包含在两种方式之一中但不包含在另一种方式中时,将顶点成对的两种方式被认为是不同的。
约束
- N 是偶数。
- 2 \leq N \leq 5000
- 1 \leq x_i, y_i \leq N
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}
输出
打印满足条件的将顶点分成对的方式的数量,取模 10^9 + 7.
示例输入 1
4 1 2 2 3 3 4
示例输出 1
2
将顶点分成对有三种可能的方式,如下所示,其中两种满足条件:中间的和右边的。

示例输入 2
4 1 2 1 3 1 4
示例输出 2
3
将顶点分成对有三种可能的方法,如下所示,并且它们都满足条件。

示例输入 3
6 1 2 1 3 3 4 1 5 5 6
示例输出 3
10
示例输入 4
10 8 5 10 8 6 5 1 5 4 8 2 10 3 6 9 2 1 7
示例输出 4
672