結果

問題 No.196 典型DP (1)
コンテスト
ユーザー sibasyun
提出日時 2024-02-24 20:36:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 144 ms / 2,000 ms
コード長 1,143 bytes
コンパイル時間 476 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 89,592 KB
最終ジャッジ日時 2024-09-29 10:16:44
合計ジャッジ時間 6,176 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import io
import sys
import bisect
import math
from itertools import permutations, combinations
from heapq import heappush, heappop
from collections import deque
from collections import defaultdict as dd
sys.setrecursionlimit(10**7+10)

# mod = 998244353
mod = 10**9+7

_INPUT = """\
6 1
0 1
0 2
1 3
2 4
2 5

"""



def main():
    N, K = map(int, input().split())
    G = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    def dfs(now, par):
        dp = [1] # 黒が0個となる場合の数
        for nxt in G[now]:
            if nxt == par:continue

            ndp = dfs(nxt, now)
            merged = [0]*(len(dp)+len(ndp)-1)

            for i in range(len(dp)):
                for j in range(len(ndp)):
                    merged[i+j] += dp[i]*ndp[j]
                    merged[i+j] %= mod
            dp = merged
        dp.append(dp[-1]) # 自分以外全部黒と、全部黒は同数
        return dp
    
    print(dfs(0, -1)[K])   
                            
if __name__ == "__main__":
    # sys.stdin = io.StringIO(_INPUT)
    main()
0