問題一覧 > 通常問題

No.1227 I hate ThREE

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 53
作問者 : tyawanmusityawanmusi / テスター : 37zigen37zigen
8 ProblemId : 4455 / 出題時の順位表
問題文最終更新日: 2020-08-30 01:40:56

元ネタ

ThREE
面白い問題です。

問題文

$N$ 頂点の木があります。頂点には $1$ から $N$ までの番号がついており、$i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

$3$ が大好きな高橋くんは、以下の条件を満たす $1$ から $C$ までの整数からなる数列 $p_1,p_2,\dots,p_N(1 \le p_i \le C)$ を探しています。

  • 隣り合う頂点の組 $(i,j)$ について、$|p_i-p_j|=3$

高橋くんのために条件を満たす数列の個数を $10^9+7$ で割った余りを求めてください。

制約

  • $2 \le N \le 1000$
  • $1 \le a_i,b_i \le N$
  • $4 \le C \le 10^9$
  • 与えられるグラフは木である

入力

$N\ C$
$a_1\ \ b_1$
$a_2\ \ b_2$
$\vdots$
$a_{N-1}\ \ b_{N-1}$

$1$ 行目には $N,C$ が空白区切りで与えられる。
$i+1(1\le i \le N-1)$ 行目には $a_i,b_i$ が空白区切りで与えられる。

出力

数列の個数を $10^9+7$ で割った余りを1行に出力してください。
最後に改行してください。

サンプル

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

$(1,4,4,1,1)$ と $(4,1,1,4,4)$ が条件を満たします。

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

サンプル1に加え、$(2,5,5,2,2)$ と $(5,2,2,5,5)$ も条件を満たします。

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。