問題一覧 > 通常問題

No.196 典型DP (1)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 149
作問者 : evimaevima
12 ProblemId : 234 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:21

問題文

$N$ 個の頂点をもつ根付き木と整数 $K$ が与えられます。この木の各頂点を白または黒で塗ることを考えます。
次の2条件をともに満たすような塗り方の個数を $1,000,000,007$ で割った余りを求めてください。
1. ちょうど $K$ 個の頂点が黒で塗られる。
2. 黒で塗られる任意の頂点 $v$ について、$v$ のどの子もまた黒で塗られる。

(用語に関しては Wikipedia を参照してください:木 (数学) - Wikipedia

入力

$N$ $K$
$a_0$ $b_0$
:
$a_{N-2}$ $b_{N-2}$

$2 \le N \le 2000,$ $0 \le K \le N$
木の各頂点には $0$ から $N-1$ の番号が割り当てられており、頂点 $0$ が木の根である。各 $i$ $(0 \le i \le N-2)$ に対し、 $a_i, b_i$ $(0 \le a_i \lt b_i \le N-1)$ は2頂点 $a_i, b_i$ が1本の辺で直接結ばれていることを表す。入力されるグラフは木であることが保証される。

出力

条件を満たす塗り方の個数を $1,000,000,007$ で割った余りを出力し、末尾で改行せよ。

サンプル

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

頂点 $3, 4, 5$ のうちいずれかひとつを黒で塗り、残りの頂点すべてを白で塗れば条件が満たされます。
頂点 $v$ が子を持たない場合、条件 "$v$ のどの子もまた黒で塗られる" が常に成立することに注意してください。

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

黒で塗られる頂点の集合が $\{1, 3\}, \{3, 4\}, \{3, 5\}, \{4, 5\}$ のいずれかであるとき、条件が満たされます。

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

黒で塗られる頂点の集合が $\{1, 3, 4\}, \{1, 3, 5\}, \{2, 4, 5\}, \{3, 4, 5\}$ のいずれかであるとき、条件が満たされます。

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