結果
問題 | No.196 典型DP (1) |
ユーザー | nsd_fb |
提出日時 | 2015-04-27 00:42:21 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 1,766 bytes |
コンパイル時間 | 1,481 ms |
コンパイル使用メモリ | 169,828 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-05 03:21:23 |
合計ジャッジ時間 | 2,764 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 1 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,944 KB |
testcase_15 | AC | 2 ms
6,940 KB |
testcase_16 | AC | 3 ms
6,944 KB |
testcase_17 | AC | 3 ms
6,940 KB |
testcase_18 | AC | 5 ms
6,940 KB |
testcase_19 | AC | 4 ms
6,940 KB |
testcase_20 | AC | 3 ms
6,940 KB |
testcase_21 | AC | 4 ms
6,940 KB |
testcase_22 | AC | 3 ms
6,944 KB |
testcase_23 | AC | 5 ms
6,944 KB |
testcase_24 | AC | 3 ms
6,940 KB |
testcase_25 | AC | 6 ms
6,944 KB |
testcase_26 | AC | 3 ms
6,940 KB |
testcase_27 | AC | 3 ms
6,940 KB |
testcase_28 | AC | 4 ms
6,940 KB |
testcase_29 | AC | 4 ms
6,940 KB |
testcase_30 | AC | 4 ms
6,944 KB |
testcase_31 | AC | 2 ms
6,940 KB |
testcase_32 | AC | 9 ms
6,940 KB |
testcase_33 | AC | 13 ms
6,940 KB |
testcase_34 | AC | 21 ms
6,944 KB |
testcase_35 | AC | 23 ms
6,940 KB |
testcase_36 | AC | 3 ms
6,940 KB |
testcase_37 | AC | 5 ms
6,944 KB |
testcase_38 | AC | 12 ms
6,944 KB |
testcase_39 | AC | 13 ms
6,940 KB |
testcase_40 | AC | 23 ms
6,940 KB |
testcase_41 | AC | 2 ms
6,940 KB |
testcase_42 | AC | 1 ms
6,940 KB |
testcase_43 | AC | 2 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> #ifdef LOCAL #include "dump.hpp" #else #define dump(...) #endif using namespace std; #define REP(i, a, b) for(int i = (a); i < int(b); ++i) #define rep(i, n) REP(i, 0, n) #define ALL(x) begin(x), end(x) template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; } template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; } typedef vector<vector<int>> graph; constexpr int mod = 1000000007; constexpr int MAX = 2000; int n, k; vector<int> G[MAX]; pair<int, vector<int>> dfs(int v, int p) { int size = 1; vector<vector<int>> dp; dp.reserve(G[v].size()); for(const auto &c : G[v]) { if(c == p) continue; const auto result = dfs(c, v); size += result.first; dp.emplace_back(move(result.second)); } if(dp.empty()) return make_pair(1, vector<int>{1, 1}); int max_idx = -1; int max_size = 0; for(int i = 0; i < dp.size(); ++i) { if(max_size < dp[i].size()) { max_idx = i; max_size = dp[i].size(); } } vector<int> res = move(dp[max_idx]); const int m = min(size, k); res.resize(m + 1, 0); for(int i = 0; i < dp.size(); ++i) { if(i == max_idx) continue; vector<int> tmp(m + 1, 0); for(int j = m; j >= 0; --j) { for(int l = dp[i].size() - 1; l >= 0; --l) { if(j + l > m) continue; tmp[j + l] = (tmp[j + l] + static_cast<long long>(res[j]) * dp[i][l]) % mod; } } res = move(tmp); } if(size <= k) res[size] += 1; dump(v, size, res); return make_pair(size, res); } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> k; for(int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; G[a].emplace_back(b); G[b].emplace_back(a); } const auto ans = dfs(0, -1); cout << ans.second[k] << endl; return EXIT_SUCCESS; }