結果
問題 | No.196 典型DP (1) |
ユーザー | nanophoto12 |
提出日時 | 2021-11-23 16:11:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 35 ms / 2,000 ms |
コード長 | 1,555 bytes |
コンパイル時間 | 4,580 ms |
コンパイル使用メモリ | 255,180 KB |
最終ジャッジ日時 | 2025-01-26 00:45:17 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> #define M_PI 3.14159265358979323846 // pi using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; typedef tuple<ll, ll, ll> t3; typedef tuple<ll, ll, ll, ll> t4; typedef tuple<ll, ll, ll, ll, ll> t5; #define rep(a,n) for(ll a = 0;a < n;a++) template<typename T> static inline void chmin(T& ref, const T value) { if (ref > value) ref = value; } template<typename T> static inline void chmax(T& ref, const T value) { if (ref < value) ref = value; } #include <atcoder/all> using namespace atcoder; typedef modint1000000007 mint; int main() { int n, k; cin >> n >> k; vector<vector<int>> g(n); rep(i, n - 1) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } vector<int> cs(n, 0); function<int(int, int)> dfs = [&](int current, int parent) { int c = 1; for (auto x : g[current]) { if (x == parent) continue; c += dfs(x, current); } cs[current] = c; return c; }; dfs(0, -1); vector<mint> dp2(k + 1, 0); dp2[k] = 1; function<void(int, int, vector<mint>&)> dfs2 = [&](int current, int parent, vector<mint>& dp) { //塗らないパターン vector<mint> temp = dp; //子供を個別に塗り分けていくパターン for (auto x : g[current]) { if (x == parent) continue; dfs2(x, current, temp); } //自分以下をすべて塗るパターン for (int x = cs[current]; x <= k; x++) { temp[x - cs[current]] += dp[x]; } dp = temp; }; dfs2(0, -1, dp2); cout << dp2[0].val() << endl; return 0; }