結果
問題 | No.196 典型DP (1) |
ユーザー | mymelochan |
提出日時 | 2022-03-06 15:33:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 852 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 90,368 KB |
最終ジャッジ日時 | 2024-07-21 00:59:21 |
合計ジャッジ時間 | 4,858 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
import sys sys.setrecursionlimit(10**4) N,K = map(int,input().split()) G = [[] for _ in range(N)] for _ in range(N-1): u,v = map(int,input().split()) G[u].append(v) G[v].append(u) visited = [0]*N size = [0]*N dp = [[] for _ in range(N)] #dp[v][k]:vの部分木でk個黒が塗られている数 MOD = 10**9+7 def dfs(cur): visited[cur] = 1 size[cur] = 1 dp_cur = [1] for nxt in G[cur]: if visited[nxt]: continue dfs(nxt) dp_nxt = dp[nxt] ndp = [0]*(size[cur]+size[nxt]-1) for i in range(size[cur]): for j in range(size[nxt]): ndp[i+j] += dp_cur[i]*dp_nxt[j] ndp[i+j] %= MOD dp_cur = ndp size[cur] += (size[nxt]-1) dp_cur.append(1) size[cur] += 1 dp[cur] = dp_cur dfs(0) print(dp[0][K]) #print(dp)