← 返回题目列表

AtCoder · arc101_c

E. 树上的丝带

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

分数: 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