問題一覧 > 通常問題

No.1075 木の上の山

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

問題文

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

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

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

入力

N K
a1 b1

aN1 bN1

入力はすべて整数
2N, K1000
1ai,biN (1iN1)
与えられるグラフは木になることが保証される

出力

山の個数を 109+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もしくは右上の雲マークをクリックしてアカウントを作成してください。