結果
問題 | No.196 典型DP (1) |
ユーザー | Kutimoti_T |
提出日時 | 2018-09-05 22:32:21 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 838 bytes |
コンパイル時間 | 1,357 ms |
コンパイル使用メモリ | 163,420 KB |
実行使用メモリ | 6,400 KB |
最終ジャッジ日時 | 2024-11-15 17:22:58 |
合計ジャッジ時間 | 2,846 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> using namespace std; using i64 = long long; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) #define all(x) x.begin(),x.end() #define int long long int N,K; vector<int> G[101010]; const i64 MOD = 1e9 + 7; vector<int> dfs(int v,int f = -1){ vector<int> res; res.push_back(1); for(int to : G[v]){ if(to == f) continue; vector<int> ret = dfs(to,v); vector<int> next(res.size() + ret.size() - 1,0); for(int i = 0;i < res.size();i++){ for(int j = 0;j < ret.size();j++){ (next[i + j] += res[i] * ret[j] % MOD) %= MOD; } } res = next; } res.push_back(1); return res; } signed main(){ cin >> N >> K; for(int i = 0;i < N - 1;i++){ int a,b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } cout << dfs(0)[K] % MOD << endl; }