No.758 VVVVV

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 19
作問者 : NoelちゃんNoelちゃん / テスター : matsu7874matsu7874
1 ProblemId : 2578 / 出題時の順位表

問題文

頂点 1 を根とする頂点数 N の順序木が与えられます。
この順序木を根から DFS するとき、「親から子に潜る移動」と「子から親に戻る移動」の2種類の移動があります、それぞれ移動 A、移動 B と呼びます。
また、この順序木を DFS するときの「移動 A から移動 B、または移動 B から移動 A に変化する回数」を M とします。
このとき、頂点数 N の順序木であって DFS 時の「移動 A から移動 B、または移動 B から移動 A に変化する回数」が M と等しくなるようなものの個数を MOD $10^9 + 7$ で求めてください。

入力

$N$
$a_1\ b_1$
$a_i\ b_i$
$a_{N - 1}\ b_{N - 1}$

一行目に頂点数 $N (1 \le N \le 10^5)$ が与えられます。
続く N - 1 行に辺が与えられます、各辺は 頂点 $a_i$ と頂点 $b_i$ を相互に結びます。
$1 \le a_i, b_i \le N$

出力

順序木の個数を MOD $10^9 + 7$ で求めてください。

サンプル

サンプル1
入力
5
1 2 
2 3
2 4
3 5
出力
6

DFS の移動を A と B で書くと。
AAABBABB となり、移動の種類が変化する回数は 3 回になります。

サンプル2
入力
10
1 2
1 3
3 4
3 5
4 6
2 7
5 8
4 9
7 10
出力
1176

サンプル3
入力
30
1 2
2 3
2 4
4 5
3 6
1 7
3 8
3 9
3 10
10 11
8 12
8 13
10 14
10 15
12 16
3 17
5 18
1 19
16 20
13 21
21 22
7 23
7 24
17 25
25 26
21 27
14 28
18 29
23 30
出力
493001124

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。