結果
問題 | No.196 典型DP (1) |
ユーザー | kei |
提出日時 | 2018-09-18 22:46:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 38 ms / 2,000 ms |
コード長 | 2,637 bytes |
コンパイル時間 | 1,529 ms |
コンパイル使用メモリ | 178,116 KB |
実行使用メモリ | 35,200 KB |
最終ジャッジ日時 | 2024-07-18 08:07:07 |
合計ジャッジ時間 | 3,022 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include "bits/stdc++.h"using namespace std;typedef long long ll;typedef pair<int, int> pii;typedef pair<ll, ll> pll;const int INF = 1e9;const ll LINF = 1e18;template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out<< Mat[i];} return out; }template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out <<it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }/*<url:https://yukicoder.me/problems/no/196>問題文=============================================================================================================================解説=============================================================================================================================*/ll N,K;vector<vector<ll>> G;vector<ll> child;const ll MOD = 1e9+7;ll child_init(ll n,ll pre){ll now = 1;for(ll next:G[n]){if(pre == next) continue;now += child_init(next, n);}return child[n] = now;}vector<pll> rec(ll n,ll pre){vector<ll> dp(N+1);dp[0] = 1;for(ll next:G[n]){if(pre == next) continue;auto T = rec(next,n);for(ll i = N; i >= 0; i--){if(dp[i] == 0) continue;for(auto p:T){if(p.first == 0) continue;(dp[i+p.first] += dp[i]*p.second)%=MOD;}// for(ll j = 1; j <= N;j++){// if(T[j] == 0) continue;// (dp[i+j] += dp[i]*T[j])%=MOD;// }}}dp[child[n]] = 1;vector<pll> ret;for(int i = 0; i <= N;i++){if(dp[i] == 0) continue;ret.push_back({i,dp[i]});}return ret;}ll solve(){cin >> N >> K;G.resize(N);child.resize(N);for(int i = 0; i < N-1;i++){ll a,b; cin >> a >> b;G[a].push_back(b);G[b].push_back(a);}child_init(0, -1);ll res = 0;auto T = rec(0,-1);for(auto p :T){if(p.first==K) res = p.second;}return res;}int main(void) {cin.tie(0); ios_base::sync_with_stdio(false);cout << solve() << endl;return 0;}