結果

問題 No.196 典型DP (1)
ユーザー norioc
提出日時 2025-04-08 02:36:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 156 ms / 2,000 ms
コード長 1,107 bytes
コンパイル時間 358 ms
コンパイル使用メモリ 81,904 KB
実行使用メモリ 80,032 KB
最終ジャッジ日時 2025-04-08 02:37:01
合計ジャッジ時間 6,360 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
adj = defaultdict(list)
for _ in range(N-1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)


def count_subtree_vertices(root):
    def dfs(v, par):
        res = 1
        for to in adj[v]:
            if to == par: continue
            res += dfs(to, v)

        subt[v] = res
        return res

    subt = [0] * N
    dfs(root, -1)
    return subt


def tree_dp(v, par):
    dp0 = [1, 0]  # 頂点 v を黒く塗らない

    for to in adj[v]:
        if to == par: continue

        r_dp0 = tree_dp(to, v)
        sz = len(dp0) + len(r_dp0) - 1
        pp0 = [0] * sz
        dp0, pp0 = pp0, dp0
        for i in range(len(pp0)):
            for j in range(len(r_dp0)):
                dp0[i+j] += pp0[i] * r_dp0[j]
                dp0[i+j] %= MOD

    nv = subt[v]
    # 頂点 v を黒くする
    dp0[nv] += 1
    dp0[nv] %= MOD
    return dp0


subt = count_subtree_vertices(root=0)
dp0 = tree_dp(0, -1)
ans = dp0[K] % MOD
print(ans)
0