#483269 (C++14) No.196 典型DP (1)

• 問題: No.196 典型DP (1)
• ユーザー: Jumbo_kpr
• 提出日時: 2020-05-18 03:44:09
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 32 ms / 2,000 ms
• コード長: 6,726 bytes
• コンパイル時間: 2,092 ms
• コンパイル使用メモリ: 132,728 KB
• 実行使用メモリ: 37,340 KB
• 最終ジャッジ日時: 2024-11-14 22:29:53
• 合計ジャッジ時間: 4,326 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	18 ms; 35,632 KB
testcase_01	AC	18 ms; 35,344 KB
testcase_02	AC	18 ms; 36,488 KB
testcase_03	AC	17 ms; 35,708 KB
testcase_04	AC	17 ms; 35,848 KB
testcase_05	AC	17 ms; 36,132 KB
testcase_06	AC	18 ms; 36,364 KB
testcase_07	AC	18 ms; 36,348 KB
testcase_08	AC	18 ms; 36,356 KB
testcase_09	AC	18 ms; 36,316 KB
testcase_10	AC	17 ms; 36,368 KB
testcase_11	AC	17 ms; 36,128 KB
testcase_12	AC	17 ms; 35,676 KB
testcase_13	AC	18 ms; 37,244 KB
testcase_14	AC	18 ms; 37,208 KB
testcase_15	AC	18 ms; 36,008 KB
testcase_16	AC	19 ms; 35,420 KB
testcase_17	AC	20 ms; 36,092 KB
testcase_18	AC	21 ms; 35,476 KB
testcase_19	AC	21 ms; 35,732 KB
testcase_20	AC	19 ms; 36,044 KB
testcase_21	AC	20 ms; 35,740 KB
testcase_22	AC	19 ms; 36,344 KB
testcase_23	AC	22 ms; 36,448 KB
testcase_24	AC	20 ms; 35,552 KB
testcase_25	AC	25 ms; 36,284 KB
testcase_26	AC	21 ms; 35,712 KB
testcase_27	AC	23 ms; 36,180 KB
testcase_28	AC	29 ms; 36,916 KB
testcase_29	AC	32 ms; 35,604 KB
testcase_30	AC	31 ms; 36,616 KB
testcase_31	AC	23 ms; 35,556 KB
testcase_32	AC	27 ms; 35,576 KB
testcase_33	AC	28 ms; 37,036 KB
testcase_34	AC	29 ms; 36,704 KB
testcase_35	AC	29 ms; 35,936 KB
testcase_36	AC	22 ms; 37,340 KB
testcase_37	AC	22 ms; 36,080 KB
testcase_38	AC	27 ms; 35,720 KB
testcase_39	AC	27 ms; 35,704 KB
testcase_40	AC	29 ms; 35,744 KB
testcase_41	AC	17 ms; 36,696 KB
testcase_42	AC	17 ms; 36,752 KB
testcase_43	AC	17 ms; 36,196 KB

ソースコード

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
//#pragma warning(disable : 4996)

#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64
#endif

#include <limits.h>
#include <math.h>
#include <time.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m - 1; i >= n; --i)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v, n) reverse(v, v + n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout << (x) << '\n'
#define pe(x) cout << (x) << " "
#define DEBUG(x) cout << #x << ": " << x << endl
#define lb(v, n) lower_bound(v.begin(), v.end(), (n))
#define ub(v, n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i, v.size()) cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template <typename T1, typename T2> inline void chmin(T1& a, T2 b) {
	if (a > b) a = b;
}
template <typename T1, typename T2> inline void chmax(T1& a, T2 b) {
	if (a < b) a = b;
}
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9+7;
constexpr int MAX = 200020;
const double pi = acos(-1);
// constexpr double EPS = 1e-10;
constexpr ll INF = 1e16;
void yes(bool c) {
	if (c)
		print("Yes");
	else
		print("No");
};

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
ll add(ll x, ll y) {
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}
ll sub(ll x, ll y) {
	x -= y;
	if (x < 0) return x + MOD;
	return x;
}
ll mult(ll x, ll y) {
	return (x * y) % MOD;
}
ll bin_pow(ll x, ll p) {
	if (p == 0) return 1;
	if (p & 1) return mult(x, bin_pow(x, p - 1));
	return bin_pow(mult(x, x), p / 2);
}

template<typename T>
struct SegmentTree {
	int n;
	T unit;
	vector<T>dat;
	function<T(T, T)> func;
	SegmentTree(const int N, T _unit, function<T(T, T)> _func)
		:unit(_unit), func(_func) {
		n = 1;
		//簡単のため、要素数を2のべき乗に
		while (n < N)n *= 2;
		dat.assign(2 * n, unit);
	}

	void update(int k, T a) {
		k += n - 1;//葉の節点
		dat[k] = a;
		//上りながら更新
		while (k > 0) {
			k = (k - 1) / 2;
			dat[k] = func(dat[k * 2 + 1], dat[k * 2 + 2]);
		}
	}
	T _query(int a, int b, int k, int l, int r) {
		//[a,b)と[l,r)が交差していなければ、funcに影響を与えない値を返す
		if (r <= a || b <= l)return unit;
		//[a,b)が[l,r)を完全に含んでいれば、この節点の値
		if (a <= l && r <= b)return dat[k];
		else {
			int vl = _query(a, b, k * 2 + 1, l, (l + r) / 2);
			int vr = _query(a, b, k * 2 + 2, (l + r) / 2, r);
			return func(vl, vr);
		}
	}
	//[a,b)
	T query(int a, int b) {
		return _query(a, b, 0, 0, n);
	}
};
//auto f = [](int a, int b) {return a + b; };
//SegmentTree<int>seg(N,0,f);

long long gcd(long long x, long long y) {
	long long m = max(x, y), n = min(x, y);
	if (n == 0)return m;
	if (m%n == 0)return n;
	else return gcd(m%n, n);
}

const int mod = 1000000007;
//const int mod = 998244353;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) :x((x%mod + mod) % mod) {}
	mint operator-() const { return mint(-x); }
	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; }
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const { return pow(mod - 2); }
	mint& operator/=(const mint a) { return *this *= a.inv(); }
	mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }




/*
mint dp[l][r][k]:=[l,r)でR-B=kとする場合の数→むり～
mint dp[i][k]:=左からi文字目まででR-B=kとする場合の数
*/
//{
//	cin >> S;
//	cin >> K;
//	dp[0][3000] = 1;
//	int N = S.size();
//	stack<int>stk;
//	int idx = 0;
//	int M = 0;
//	REP(i, N) {
//		if (S[i] == '(') {
//			stk.push(i);
//			idx++;
//		}
//		else {
//			int now = stk.top();
//			stk.pop();
//			if (!stk.empty()) {
//				int par = stk.top();
//				G[par].push_back(now);
//			}
//		}
//	}
//	dfs(0, 0);
//}

vector<int>G[2020];

int siz[2020];
int dfs(int n, int pre) {
	int res = 1;
	for (auto nxt : G[n]) {
		if (nxt == pre)continue;
		res += dfs(nxt, n);
	}
	return siz[n] = res;
}
int N, K;
mint dp[2020][2020];//頂点iの部分木のうちj個を黒く塗る場合の数
void rec(int n, int pre) {
	//cerr << "n:" << n << endl;
	for (auto nxt : G[n]) {
		if (nxt == pre)continue;
		rec(nxt, n);
	}
	int sum = 1;
	dp[n][0] = 1;
	for (auto nxt : G[n]) {
		if (nxt == pre)continue;
		vector<mint>tmp(2020);
		REP(i, sum + 1) {
			REP(j, siz[nxt] + 1) {
				if (i + j > K)break;
				tmp[i + j] += dp[n][i] * dp[nxt][j];
			}
		}
		sum += siz[nxt];
		REP(i, sum + 1)dp[n][i] = tmp[i];
	}
	dp[n][siz[n]] = dp[n][siz[n] - 1];
}

void solve() {
	cin >> N >> K;
	REP(i, N - 1) {
		int u, v; cin >> u >> v;
		//u--, v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(0, 0);
	rec(0, 0);
	print(dp[0][K]);
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	// int q;
	// cin >> q;
	// while (q--)
	solve();
}