結果
問題 | No.196 典型DP (1) |
ユーザー | 🐬hec |
提出日時 | 2015-07-30 17:07:52 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 1,656 bytes |
コンパイル時間 | 1,372 ms |
コンパイル使用メモリ | 162,840 KB |
実行使用メモリ | 66,688 KB |
最終ジャッジ日時 | 2024-07-17 22:37:10 |
合計ジャッジ時間 | 3,243 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}template<class T> inline T sqr(T x) {return x*x;}typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<string> vs;typedef pair<int, int> pii;typedef long long ll;#define all(a) (a).begin(),(a).end()#define rall(a) (a).rbegin(), (a).rend()#define pb push_back#define mp make_pair#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)#define exist(s,e) ((s).find(e)!=(s).end())#define range(i,a,b) for(int i=(a);i<(b);++i)#define rep(i,n) range(i,0,n)#define clr(a,b) memset((a), (b) ,sizeof(a))#define dump(x) cerr << #x << " = " << (x) << endl;#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;const double eps = 1e-10;const double pi = acos(-1.0);const ll INF =1LL << 62;const int inf =1 << 29;const ll mod= 1000000007;const int nmax=2010;vi graph[nmax];int num[nmax];ll dp[nmax][nmax];void dfs(int v,int p){for(auto &v2:graph[v]) if(v2!=p) dfs(v2,v);rep(i,nmax) dp[v][i]=0;dp[v][0]=1LL,num[v]=0;for(auto &v2:graph[v])if(v2!=p) {ll dp2[nmax];rep(i,nmax) dp2[i]=0;rep(i,num[v]+1)rep(j,num[v2]+1)dp2[i+j]=(dp2[i+j]+dp[v][i]*dp[v2][j])%mod;rep(i,nmax) dp[v][i]=dp2[i];num[v]+=num[v2];}num[v]++,dp[v][num[v]]=1;return;}int main(void){int N,K;cin >> N >> K;rep(i,N-1){int a,b;cin >> a >> b;graph[a].pb(b);graph[b].pb(a);}dfs(0,-1);cout << dp[0][K] << endl;return 0;}