結果
問題 | No.196 典型DP (1) |
ユーザー | snuke |
提出日時 | 2015-04-26 22:34:38 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 2,474 bytes |
コンパイル時間 | 812 ms |
コンパイル使用メモリ | 83,412 KB |
実行使用メモリ | 40,516 KB |
最終ジャッジ日時 | 2024-07-05 03:02:33 |
合計ジャッジ時間 | 3,054 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <cstdio>#include <algorithm>#include <stack>#include <queue>#include <deque>#include <vector>#include <string>#include <string.h>#include <cstdlib>#include <ctime>#include <cmath>#include <map>#include <set>#include <iostream>#include <sstream>#include <cctype>#define fi first#define se second#define rep(i,n) for(int i = 0; i < n; ++i)#define rrep(i,n) for(int i = 1; i <= n; ++i)#define drep(i,n) for(int i = n-1; i >= 0; --i)#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define rng(a) a.begin(),a.end()#define maxs(x,y) x = max(x,y)#define mins(x,y) x = min(x,y)#define pb push_back#define sz(x) (int)(x).size()#define pcnt __builtin_popcount#define snuke srand((unsigned)clock()+(unsigned)time(NULL));using namespace std;typedef long long int ll;typedef pair<int,int> P;inline int in() { int x; scanf("%d",&x); return x;}const int MX = 100005, INF = 1000010000;const ll LINF = 1000000000000000000ll;const double eps = 1e-10;const int di[] = {-1,0,1,0}, dj[] = {0,-1,0,1}; //^<v>// Mod intconst int mod = 1000000007;struct mint{ll x;mint():x(0){}mint(ll x):x((x%mod+mod)%mod){}mint operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}mint operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}mint operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}mint operator+(const mint& a)const{ return mint(*this) += a;}mint operator-(const mint& a)const{ return mint(*this) -= a;}mint operator*(const mint& a)const{ return mint(*this) *= a;}bool operator==(const mint& a)const{ return x == a.x;}};//typedef vector<int> vi;typedef vector<mint> vm;typedef vector<vm> vvm;int n, k;vi to[MX];int s[MX];vvm dp[MX];void dfs(int v, int p=-1) {s[v] = 1;dp[v] = vvm(2,vm(2));dp[v][0][0] = 1;dp[v][1][1] = 1;for (int u : to[v]) {if (u == p) continue;dfs(u,v);vvm a = dp[v];vvm& b = dp[u];rep(i,2) dp[v][i] = vm(s[v]+s[u]+1,0);rep(i,s[v]+1)rep(j,s[u]+1) {dp[v][0][i+j] += a[0][i]*b[0][j];dp[v][0][i+j] += a[0][i]*b[1][j];dp[v][1][i+j] += a[1][i]*b[1][j];}s[v] += s[u];}}int main(){cin >> n >> k;rep(i,n-1) {int a, b;cin >> a >> b;to[a].pb(b);to[b].pb(a);}dfs(0);mint ans = 0;rep(i,2) ans += dp[0][i][k];cout << ans.x << endl;return 0;}