No.1075 木の上の山
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 34
作問者 :
Kiri8128
/ テスター :
nmnmnmnmnmnmnm
タグ : / 解いたユーザー数 34
作問者 :
Kiri8128
/ テスター :
nmnmnmnmnmnmnm
問題文最終更新日: 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$ を含む）に書き込まれた整数を順に並べた数列が広義単調減少になる （※）
入力
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。