D - なめらかな木
Editorial
/


Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1100 点
問題文
N 頂点の木が与えられます。 頂点には番号 1, 2, ..., N がついており、i 番目の辺は頂点 a_i, b_i をつないでいます。
木の頂点に整数 1, 2, ..., N をそれぞれ 1 個ずつ書き込むことを考えます。 頂点 i に書き込んだ値を c_i とします。
ただし、頂点 u, v が隣り合っている、つまり辺 (u, v) が存在するならば、 |c_u - c_v| ≦ 2 を満たしていないといけません。(10:53)変数名を修正しました
このような書き込み方は何通りあるでしょうか、1000000007 = 10^9 + 7 で割った余りを求めてください。
制約
- 1 ≦ N ≦ 50
- 1 ≦ a_i, b_i ≦ N
- 入力は木になっている
入力
入力は以下の形式で標準入力から与えられる。
N a_1 b_1 a_2 b_2 : a_{N-1} b_{N-1}
出力
求めた答えを出力してください。
入力例 1
5 1 2 1 3 1 4 1 5
出力例 1
24
頂点 1 に 3 を書き込む必要があります。
入力例 2
6 1 2 1 3 1 4 1 5 1 6
出力例 2
0
入力例 3
4 1 2 2 3 3 4
出力例 3
12
入力例 4
7 1 3 2 3 4 3 5 4 5 6 5 7
出力例 4
48