結果
問題 |
No.196 典型DP (1)
|
ユーザー |
|
提出日時 | 2022-06-28 19:57:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 854 bytes |
コンパイル時間 | 1,872 ms |
コンパイル使用メモリ | 178,580 KB |
実行使用メモリ | 26,624 KB |
最終ジャッジ日時 | 2024-11-21 13:41:43 |
合計ジャッジ時間 | 3,604 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ int n, k; cin >> n >> k; vector<vector<int>> g(n); vector<vector<ll>> dp(n + 1); for(int i = 1, u, v; i < n; i++){ cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } function<void(int,int)> dfs = [&](int v, int p){ dp[v].resize(1, 1); for(auto &&u:g[v]){ if(u == p)continue; dfs(u, v); vector<ll> ndp(dp[v].size() + dp[u].size() - 1); for(int j = 0; j < dp[v].size(); j++){ for(int k = 0; k < dp[u].size(); k++){ (ndp[j + k] += dp[v][j] * dp[u][k]) %= 1000000007; } } swap(dp[v], ndp); } dp[v].push_back(1); }; dfs(0, -1); cout << dp[0][k] << endl; }