結果
問題 | No.196 典型DP (1) |
ユーザー | cubinglover |
提出日時 | 2022-11-26 20:53:52 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 2,104 bytes |
コンパイル時間 | 2,058 ms |
コンパイル使用メモリ | 213,036 KB |
実行使用メモリ | 19,584 KB |
最終ジャッジ日時 | 2024-10-03 04:06:25 |
合計ジャッジ時間 | 3,726 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define repl(i, l, r) for (int i = (l); i < (int)(r); ++i) #define rep(i, n) repl(i, 0, n) #define CST(x) cout << fixed << setprecision(x) #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() using ll = long long; constexpr ll MOD = 1e9 + 7; constexpr int inf = 1e9 + 10; constexpr ll INF = (ll)4e18 + 10; constexpr int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0}; constexpr int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0}; const double PI = acos(-1); template <typename T> using MaxHeap = priority_queue<T>; template <typename T> using MinHeap = priority_queue<T, vector<T>, greater<T>>; template <typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template <typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } template <typename T> inline void yn(const T &a) { ((a) ? (cout << "Yes" << endl) : (cout << "No" << endl)); } template <typename T> inline void YN(const T &a) { ((a) ? (cout << "YES" << endl) : (cout << "NO" << endl)); } int main() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); int n, k; cin >> n >> k; vector<vector<int>> G(n); rep(i, n - 1) { int a, b; cin >> a >> b; G[a].emplace_back(b), G[b].emplace_back(a); } vector<vector<ll>> dp(n); auto f = [&G, &dp](auto self, const auto &v, const auto &p) -> int { int res = 1; dp[v].assign(res + 1, 0); dp[v][0] = 1; for (const auto &to : G[v]) { if (to == p) continue; res += self(self, to, v); } for (const auto &to : G[v]) { if (to == p) continue; vector<ll> merged(sz(dp[v]) + sz(dp[to]) - 1); rep(i, sz(dp[v])) rep(j, sz(dp[to])) { merged[i + j] += dp[v][i] * dp[to][j] % MOD; merged[i + j] %= MOD; } dp[v] = merged; } dp[v][res] = 1; return res; }; f(f, 0, -1); cout << dp[0][k] << endl; return 0; }