問題一覧 > 通常問題

No.1075 木の上の山

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 28
作問者 : Kiri8128Kiri8128 / テスター : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
4 ProblemId : 4352 / 出題時の順位表
問題文最終更新日: 2020-06-13 00:32:01

問題文

高橋くんは木と山が大好きです。 $N$ 頂点の木があり、頂点には $1$ から $N$ までの番号が振られています。辺は $N-1$ 本あり、 $i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。この木の上の「山」とは、各頂点に $1$ 以上 $K$ 以下の整数を書き込む方法であって、次の条件を満たすものです。

  • ある $i\ (1\le i\le N)$ が存在し、任意の $j\ (1\le j\le N,\ i\neq j)$ に対し、木の上の頂点をたどって頂点 $i$ から頂点 $j$ に最短経路で向かうとき、通過する頂点(頂点 $i$ と頂点 $j$ を含む)に書き込まれた整数を順に並べた数列が広義単調減少になる (※)

山の個数を $1000000007\ (=10^9+7)$ で割った余りを出力してください。

入力

$N\ K$
$a_1\ b_1$
$\vdots$
$a_{N-1}\ b_{N-1}$

入力はすべて整数
$2\le N,\ K \le 1000$
$1\le a_i, b_i\le N\ (1\le i\le N-1)$
与えられるグラフは木になることが保証される

出力

山の個数を $10^9+7$ で割った余りを出力してください。

サンプル

サンプル1
入力
3 2
1 2
2 3
出力
7

各頂点に $1$ または $2$ を書く方法は $8$ 通りありますが、このうち頂点 1, 2, 3 に順に 2 - 1 - 2 と書き込む方法 以外 すべて条件を満たします。

例えば 1 - 2 - 1 と書き込む方法は「山」です。これは(※)において $i=2$ と取ると条件を満たすことから分かります。なお 2 - 2 - 1 と書き込む方法は(※)において $i=1$ としても $i=2$ としても条件を満たしますが、1回しかカウントしないことに注意してください。

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

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