[ARC101E] Ribbons on Tree

## 题目描述 给定一个大小为 $n$ 的树，保证 $n$ 为偶数且小于 $5000$ 您需要给树上的点两两配对，对于一组对子 $(u,v)$，在树上将 $u\to v$ 的路径染色，定义一个配对方案合法当且仅当所有边都有颜色。 求方案数对 $10^9+7$ 取模。 ## 说明/提示 $\begin{array}{l}2\le N\le 5000\\2\mid N\\\text{保证输入的一定是一棵树}\end{array}$ **样例1解释**  **样例2解释** 合法的$3$种情况如下： 

[problemUrl]: https://atcoder.jp/contests/arc101/tasks/arc101_c $ N $ を偶数とします。 $ N $ 頂点の木があります。 頂点には $ 1,\ 2,\ ...,\ N $ と番号が振られています。 各 $ i $ ($ 1\ \leq\ i\ \leq\ N\ -\ 1 $) について、$ i $ 番目の辺は頂点 $ x_i $ と $ y_i $ を結んでいます。 すぬけ君は、次のようにして木をリボンで飾りつけようと思っています。 まず、$ N $ 個の頂点を $ N\ /\ 2 $ 組のペアに分けます。 このとき、各頂点はちょうど $ 1 $ つのペアに属さなければなりません。 次に、各ペア $ (u,\ v) $ について、$ 1 $ 本のリボンを $ u $-$ v $ 間の最短パスに含まれるすべての辺を通るように張ります。 すぬけ君はペアの分け方を工夫し、「どの辺にも少なくとも $ 1 $ 本のリボンが張られている」という条件が成り立つようにしようとしています。 条件が成り立つようなペアの分け方は何通りでしょうか？ $ 10^9\ +\ 7 $ で割った余りを求めてください。 ただし、$ 2 $ 通りのペアの分け方が異なるとは、あるペアが一方には含まれるが他方には含まれないことを言います。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ : $ $ x_{N\ -\ 1} $ $ y_{N\ -\ 1} $

条件が成り立つようなペアの分け方は何通りか？ $ 10^9\ +\ 7 $ で割った余りを出力せよ。

4
1 2
2 3
3 4

2

4
1 2
1 3
1 4

3

6
1 2
1 3
3 4
1 5
5 6

10

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

672

### 制約 - $ N $ は偶数である。 - $ 2\ \leq\ N\ \leq\ 5000 $ - $ 1\ \leq\ x_i,\ y_i\ \leq\ N $ - 与えられるグラフは木である。 ### Sample Explanation 1 ペアの分け方は次図の $ 3 $ 通りであり、右側の $ 2 $ 通りが条件を満たします。 !\[\](https://img.atcoder.jp/arc101/2d7584d2e0736f746aa9d54e1bf31e28.png) ### Sample Explanation 2 ペアの分け方は次図の $ 3 $ 通りであり、すべて条件を満たします。 !\[\](https://img.atcoder.jp/arc101/2de530ed2e64d0161ee6b989d1946261.png)