結果
問題 | No.196 典型DP (1) |
ユーザー | バイト |
提出日時 | 2019-01-31 14:39:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 410 ms / 2,000 ms |
コード長 | 31,928 bytes |
コンパイル時間 | 3,293 ms |
コンパイル使用メモリ | 216,428 KB |
実行使用メモリ | 84,608 KB |
最終ジャッジ日時 | 2024-11-15 17:04:36 |
合計ジャッジ時間 | 16,704 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
//注意点//Tは3つの値を持つ構造//だがワイルドカードとしても使っている#include <bits/stdc++.h>using namespace std;//@起動時struct initon {initon() {cin.tie(0);ios::sync_with_stdio(false);cout.setf(ios::fixed);cout.precision(16);};} __initon;//@必須構造struct T {int f, s, t;T() { f = -1, s = -1, t = -1; }T(int f, int s, int t) : f(f), s(s), t(t) {}bool operator<(const T &r) const {return f != r.f ? f < r.f : s != r.s ? s < r.s : t < r.t;//return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; 大きい順}bool operator>(const T &r) const {return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t;//return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; 小さい順}int operator[](int i) {assert(i < 3);return i == 0 ? f : i == 1 ? s : t;}};//@マクロ省略系 型,構造#define int long long#define ll long long#define double long double#define ull unsigned long longusing dou = double;using itn = int;using str = string;using bo= bool;using P = pair<int, int>;#define F first#define S second#define vec vector#define con continue#define bre break#define brk break#define is ==#define rs resize//マクロ省略系 コンテナusing vi = vector<int>;#define vvi(a, b, c) vec<vi> a(b,vi(c))using vb = vector<bool>;#define vvb(a, b, c) vec<vb> a(b,vb(c))using vs = vector<string>;#define vvs(a, b, c) vec<vs> a(b,vs(c))using vl = vector<ll>;#define vvl(a, b, c) vec<vl> a(b,vl(c))using vd = vector<double>;#define vvd(a, b, c) vec<vd> a(b,vd(c))using vc=vector<char>;#define vvc(a, b, c) vec<vc> a(b,vc(c))using vp = vector<P>;#define vvp(a, b, c) vec<vp> a(b,vp(c))using vt = vector<T>;#define vvt(a, b, c) vec<vt> a(b,vt(c))#define v3i(a, b, c, d) vector<vector<vi>> a(b, vector<vi>(c, vi(d)))#define v3d(a, b, c, d) vector<vector<vd>> a(b, vector<vd>(c, vd(d)))#define v3m(a, b, c, d) vector<vector<vm>> a(b, vector<vm>(c, vm(d)))#define PQ priority_queue<ll, vector<ll>, greater<ll> >using seti = set<int>;#define uset unordered_set#define mset multiset#define umap unordered_map#define mmap multimap//マクロ 繰り返し#define _overloadrep(_1, _2, _3, name, ...) name# define _rep(i, n) for(int i = 0; i < n ; i++)#define repi(i, m, n) for(int i = m; i < n ; i++)#define rep(...) _overloadrep(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)#define _rer(i, n) for(int i = n; i >= 0 ; i--)#define reri(i, m, n) for(int i = m; i >= n ; i--)#define rer(...) _overloadrep(__VA_ARGS__,reri,_rer,)(__VA_ARGS__)#define fora(a, b) for(auto&& a : b)#define forg(gi, ve) if (ve.size())for (int gi = 0, f = ve[gi].from, t = ve[gi].to, c = ve[gi].cost; gi < ve.size(); gi++,f = ve[gi].from, t =ve[gi].to, c = ve[gi].cost)//マクロ 定数#define k4 10101#define k5 101010#define k6 1010101#define k7 10101010const int inf = (int) 1e9 + 100;const ll linf = (ll) 1e18 + 100;const double eps = 1e-9;const int y4[] = {-1, 1, 0, 0};const int x4[] = {0, 0, -1, 1};const int y8[] = {0, 1, 0, -1, -1, 1, 1, -1};const int x8[] = {1, 0, -1, 0, 1, -1, 1, -1};//マクロ省略形 関数等#define arsz(a) (sizeof(a)/sizeof(a[0]))#define sz(a) (a.size())#define mp make_pair#define pb push_back#define pf push_front#define eb emplace_back#define all(a) (a).begin(),(a).end()#define rall(a) (a).rbegin(),(a).rend()//@拡張系 こう出来るべきというもの//埋め込み 存在を意識せずに機能を増やされているもの// 境界チェック付きvectornamespace std_vector_bounds_checking {using namespace std;template<class T, class A = std::allocator<T>> struct vector : std::vector<T, A> {using std::vector<T, A>::vector;typename std::vector<T>::reference operator[](typename std::vector<T>::size_type n) {return this->at(n);}};}namespace std {template<> class hash<std::pair<signed, signed>> {public:size_t operator()(const std::pair<signed, signed> &x) const {return hash<ll>()(((ll) x.first << 32) + x.second);}};template<> class hash<std::pair<ll, ll>> {public:size_t operator()(const std::pair<ll, ll> &x) const {return hash<ll>()(((ll) x.first << 32) + x.second);}};}template<typename T> istream &operator>>(istream &iss, vector<T> &vec) {for (T &x: vec) iss >> x;return iss;}template<typename T> ostream &operator<<(ostream &os, vector <T> &vec) {for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");return os;}template<typename V, typename H> void resize(vector<V> &vec, const H head) { //再帰の終端。 可変長templateの長さが 0 になるとこっちが呼ばれる。vec.resize(head);}template<typename V, typename H, typename ... T> void resize(vector<V> &vec, const H &head, const T ... tail) {vec.resize(head);for (auto &v: vec) resize(v, tail...);}template<class T> T pop(set<T> &set) {T res = *set.begin();set.erase(set.find(res));return res;}template<class T> T pop(mset<T> &set) {T res = *set.begin();set.erase(set.find(res));return res;}template<class T> T popBack(set<T> &set) {T res = *set.rbegin();set.erase(set.find(res));return res;}template<class T> T popBack(mset<T> &set) {T res = *set.rbegin();set.erase(set.find(res));return res;}template<class T> inline void sort(vector<T> &a) { sort(a.begin(), a.end()); };template<class T> inline void rsort(vector<T> &a) { sort(a.begin(), a.end(), greater<T>()); };template<class T> inline void sort(vector<T> &a, int len) { sort(a.begin(), a.begin() + len); };template<class T> inline void rsort(vector<T> &a, int len) { sort(a.begin(), a.begin() + len, greater<T>()); };template<class T> inline void sort2(vector<vector<T>> &a) { for (int i = 0, n = a.size(); i < n; i++)sort(a[i]); }template<class T> inline void rsort2(vector<vector<T>> &a) { for (int i = 0, n = a.size(); i < n; i++)rsort(a[i]); }template<typename A, size_t N, typename T> void fill(A (&a)[N], const T &v) { rep(i, N)a[i] = v; }template<typename A, size_t N, size_t O, typename T> void fill(A (&a)[N][O], const T &v) { rep(i, N)rep(j, O)a[i][j] = v; }template<typename A, size_t N, size_t O, size_t P, typename T> void fill(A (&a)[N][O][P], const T &v) { rep(i, N)rep(j, O)rep(k, P)a[i][j][k] = v; }template<typename A, size_t N, size_t O, size_t P, size_t Q, typename T> void fill(A (&a)[N][O][P][Q], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)a[i][j][k][l] = v; }template<typename A, size_t N, size_t O, size_t P, size_t Q, size_t R, typename T> void fill(A (&a)[N][O][P][Q][R], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)a[i][j][k][l][m] = v; }template<typename A, size_t N, size_t O, size_t P, size_t Q, size_t R, size_t S, typename T> void fill(A (&a)[N][O][P][Q][R][S], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)rep(n, S)a[i][j][k][l][m][n] = v; }template<typename V, typename T> void fill(V &x, const T &val) { x = val; }template<typename V, typename T> void fill(vector<V> &vect, const T &val) { for (auto &v: vect) fill(v, val); }//@汎用便利関数 入力template<typename T = int> T in() {T x;cin >> x;return (x);}string sin() { return in<string>(); }double din() { return in<double>(); }ll lin() { return in<ll>(); }#define na(a, n) rep(i,n) cin >> a[i];#define nad(a, n) rep(i,n) cin >> a[i], a[i]--;#define na3(a, b, c, n) rep(i, n)cin >> a[i] >> b[i] >> c[i];#define add2(a, b, n) rep(i, n)a.pb(in()),b.pb(in());#define add2d(a, b, n) rep(i, n)a.pb(in()-1),b.pb(in()-1);#define add3(a, b, c, n) rep(i, n)a.pb(in()),b.pb(in()),c.pb(in());#define add3d(a, b, c, n) rep(i, n)a.pb(in()-1),b.pb(in()-1),c.pb(in());#define na2(a, b, n) rep(i, n)cin >> a[i] >> b[i];#define nt(a, h, w) rep(hi,h)rep(wi,w) cin >> a[hi][wi];#define ntd(a, h, w) rep(hi,h)rep(wi,w) cin >> a[hi][wi], a[hi][wi]--;#define ntp(a, h, w) fill(a,'#');rep(hi,1,h+1)rep(wi,1,w+1) cin >> a[hi][wi];#define addn(a, n) a.resize(n);na(a,n);#define addnd(a, n) a.resize(n);na(a,n);rep(i,n)a[i]--;//汎用便利関数 出力template<class T> void out(T x) { typeid(x) == typeid(double) ? cout << fixed << setprecision(10) << x << endl : cout << x << endl; }//デバッグ#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';//よく使うクラス、構造体class UnionFind {public:vi par, rank, sizes;int n, trees;UnionFind(int n) : n(n), trees(n) {par.resize(n), rank.resize(n), sizes.resize(n);rep(i, n)par[i] = i, sizes[i] = 1;}int root(int x) {if (par[x] == x)return x;else return par[x] = root(par[x]);}int find(int x) { return root(x); }void unite(int x, int y) {x = root(x);y = root(y);if (x == y)return;if (rank[x] < rank[y])swap(x, y);trees--;par[y] = x;sizes[x] += sizes[y];if (rank[x] == rank[y])rank[x]++;}bool same(int x, int y) { return root(x) == root(y); }int size(int x) { return sizes[root(x)]; }//順不同 umapなのでvec<vi> sets() {vec<vi> res(trees);umap<int, vi> map;rep(i, n) map[root(i)].push_back(i);int i = 0;for (auto &&p:map) {int r = p.F;res[i].push_back(r);for (auto &&v:p.S) {if (r == v)continue;res[i].push_back(v);}i++;}return res;}};//MOD関連ll MOD = (int) 1e9 + 7;int mpow(int v, ll a) {ll x = v, n = a, res = 1;while (n) {if (n & 1)res = (res * x) % MOD;x = (x * x) % MOD;n >>= 1;}return res;}class mint {private:ll v;public:static ll mod(ll a) { return (a % MOD + MOD) % MOD; }mint(ll a = 0) { this->v = mod(a); };mint(const mint &a) { v = a.v; }mint operator+(const mint &a) { return mint(v + a.v); }mint operator+(const ll a) { return mint(v + a % MOD); }mint operator+(const signed a) { return mint(v + a % MOD); }friend mint operator+(const ll a, const mint &b) { return mint(a % MOD + b.v); }void operator+=(const mint &a) { v = (v + a.v) % MOD; }void operator+=(const ll a) { v = mod(v + a % MOD); }void operator+=(const signed a) { v = mod(v + a % MOD); }friend void operator+=(ll &a, const mint &b) { a = mod(a % MOD + b.v); }mint operator-(const mint &a) { return mint(v - a.v); }mint operator-(const ll a) { return mint(v - a % MOD); }mint operator-(const signed a) { return mint(v - a % MOD); }friend mint operator-(const ll a, const mint &b) { return mint(a % MOD - b.v); }void operator-=(const mint &a) { v = mod(v - a.v); }void operator-=(const ll a) { v = mod(v - a % MOD); }void operator-=(const signed a) { v = mod(v - a % MOD); }friend void operator-=(ll &a, const mint &b) { a = mod(a % MOD - b.v); }mint operator*(const mint &a) { return mint(v * a.v); }mint operator*(const ll a) { return mint(v * (a % MOD)); }mint operator*(const signed a) { return mint(v * (a % MOD)); }friend mint operator*(const ll a, const mint &b) { return mint(a % MOD * b.v); }void operator*=(const mint &a) { v = (v * a.v) % MOD; }void operator*=(const ll a) { v = mod(v * (a % MOD)); }void operator*=(const signed a) { v = mod(v * (a % MOD)); }friend void operator*=(ll &a, const mint &b) { a = mod(a % MOD * b.v); }mint operator/(const mint &a);mint operator/(const ll a);mint operator/(const signed a);friend mint operator/(const ll a, const mint &b);void operator/=(const mint &a);void operator/=(const ll a);void operator/=(const signed a);friend void operator/=(ll &a, const mint &b);mint operator^(const mint &a) { return mpow(v, a.v); };mint operator^(const ll a) { return mpow(v, a); };mint operator^(const signed a) { return mpow(v, a); };friend mint operator^(const ll a, const mint &b) { return mpow(a, b.v); };void operator^=(const mint &a) { v = mpow(v, a.v); }void operator^=(const ll a) { v = mpow(v, a); }void operator^=(const signed a) { v = mpow(v, a); }//単項演算子mint operator+() { return *this; }mint operator++() {v++;return *this;}mint operator++(signed d) {mint res = *this;v++;return res;}mint operator-() { return operator*(-1); }mint operator--() {v++;return *this;}void operator--(signed d) {mint res = *this;v++;}bool operator==(mint &a) { return v == a.v; }bool operator==(signed a) { return v == a; }friend bool operator==(signed a, mint &b) { return a == b.v; }bool operator!=(mint &a) { return v != a.v; }bool operator!=(signed a) { return v != a; }friend bool operator!=(signed a, mint &b) { return a != b.v; }operator int() { return v; }};const int setModMax = 510000;mint fac[setModMax], finv[setModMax], inv[setModMax];void setMod() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < setModMax; 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;}}mint minv(ll a) {if (fac[0] == 0)setMod();if (a < setModMax) return inv[a];a %= MOD;ll b = MOD, x = 1, y = 0;while (b) {ll t = a / b;a -= t * b;swap(a, b);x -= t * y;swap(x, y);}return (x % MOD + MOD) % MOD;}mint mint::operator/(const mint &a) { return mint(v * minv(a.v)); }mint mint::operator/(const ll a) { return mint(v * minv(a)); }mint mint::operator/(const signed a) { return mint(v * minv(a)); }mint operator/(const ll a, const mint &b) { return mint(a % MOD * minv(b.v)); }void mint::operator/=(const mint &a) { v = (v * minv(a.v)) % MOD; }void mint::operator/=(const ll a) { v = mod(v * minv(a)); }void mint::operator/=(const signed a) { v = mod(v * minv(a)); }void operator/=(ll &a, const mint &b) { a = mint::mod(a % MOD * minv(b.v)); }using vm=vector<mint>;#define vvm(a, b, c) vec<vm> a(b,vm(c))bool isPrime[4010101];vi primes;void setPrime() {fill(isPrime, true);int len = sizeof(isPrime) / sizeof(isPrime[0]);isPrime[0] = isPrime[1] = false;for (int i = 2; i <= sqrt(len) + 5; ++i) {if (!isPrime[i])continue;for (int j = 2; i * j < len; ++j) {isPrime[i * j] = false;}}rep(i, len)if (isPrime[i])primes.pb(i);}mint com(ll n, ll r) {if (n < r || n < 0 || r < 0)return 0;if (fac[0] == 0)setMod();return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;}//便利関数void ole() {string a = "a";rep(i, 30)a += a;rep(i, 1 << 17)cout << a << endl;cout << "OLE 出力長制限超過" << endl;exit(0);}void tle() { while (inf)cout << inf << endl; }ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }bool equal(double a, double b) { return fabs(a - b) < eps; }ll reverse(ll a) {ll res = 0;while (a) {res *= 10;res += a % 10;a /= 10;}return res;}ll ceil(ll a, ll b) {if (b == 0) {ole();return -1;} else return (a + b - 1) / b;}ll sqrt(ll a) {if (a < 0)ole();ll res = (ll) std::sqrt(a);while (res * res < a)res++;return res;}double log(double e, double x) { return log(x) / log(e); }ll sig(ll t) { return (1 + t) * t / 2; }ll sig(ll s, ll t) { return (s + t) * (t - s + 1) / 2; }vi divisors(int v) {vi res;for (int i = 1; i <= sqrt(v); ++i) {if (v % i == 0) {res.pb(i);if (i != v / i)res.pb(v / i);}}return res;}vi factorization(int v) {int tv = v;vi res;if (!isPrime[2])setPrime();for (auto &&p :primes) {if (v % p == 0)res.push_back(p);while (v % p == 0) {v /= p;}if (v == 1 || p * p > tv)break;}if (v > 1)res.pb(v);return res;}unordered_map<int, int> factorizationMap(int v) {int tv = v;unordered_map<int, int> res;if (!isPrime[2])setPrime();for (auto &&p :primes) {while (v % p == 0) {res[p]++;v /= p;}if (v == 1 || p * p > tv)break;}if (v > 1)res[v]++;return res;}int get(int a, int keta) { return (a / (int) pow(10, keta)) % 10; }int keta(int v) {int cou = 0;while (v) { cou++, v %= 10; }return cou;}template<class T> void imo(vector<T> &v) {int n = v.size();rep(i, n - 1)v[i + 1] += v[i];}//変換系template<class T, class U> vector<U> keys(map<T, U> a) {vector<U> res;for (auto &&k :a)res.pb(k.F);return res;}template<class T, class U> vector<U> keys(umap<T, U> a) {vector<U> res;for (auto &&k :a)res.pb(k.F);return res;}template<class T, class U> vector<T> values(map<T, U> a) {vector<T> res;for (auto &&k :a)res.pb(k.S);return res;}template<class T, class U> vector<T> values(umap<T, U> a) {vector<T> res;for (auto &&k :a)res.pb(k.S);return res;}vi list(int a) {vi res;while (a) {res.insert(res.begin(), a % 10);a /= 10;}return res;}template<class T, class U> bool chmax(T &a, const U &b) {if (a < b) {a = b;return true;}return false;}template<class T, class U> bool chmin(T &a, const U &b) {if (b < a) {a = b;return true;}return false;}template<class T> T min(T a, signed b) {return a < b ? a : b;}template<class T> T max(T a, signed b) {return a < b ? b : a;}template<class T> T min(vector<T> a) {return *min_element(all(a));}template<class T> T max(vector<T> a) {return *max_element(all(a));}template<class T> T min(T a[]) {T res = a[0];rep(i, arsz(a))chmin(res, a[i]);return res;}template<class T> T max(T a[]) {T res = a[0];rep(i, arsz(a))chmax(res, a[i]);return res;}template<class T> T sum(vector<T> &v, int len = -1) {if (len == -1)len = v.size();T res = 0;chmin(len, v.size());rep(i, len)res += v[i];return res;}template<class T> T sum(vector<vector<T>> &v, int h = -1, int w = -1) {if (h == -1)h = v.size();if (w == -1)w = v[0].size();T res = 0;chmin(h, v.size());chmin(w, v[0].size());rep(i, h)rep(j, w)res += v[i][j];return res;}P sump(vp &v, int len = -1) {if (len == -1)len = v.size();P res = {0, 0};chmin(len, v.size());rep(i, len) {res.F += v[i].F;res.S += v[i].S;}return res;}///要素が0の時、返り値は0か1かtemplate<class T> T mul(vector<T> &v, int len = -1) {if (len == -1)len = v.size();T res = 1;chmin(len, v.size());rep(i, len)res *= v[i];return res;}void clear(PQ &q) { while (q.size())q.pop(); }template<class T> void clear(queue<T> &q) { while (q.size())q.pop(); }template<class T> T *negarr(int size) {T *body = (T *) malloc((size * 2 + 1) * sizeof(T));return body + size;}template<class T> T *negarr2(int h, int w) {double **dummy1 = new double *[2 * h + 1];double *dummy2 = new double[(2 * h + 1) * (2 * w + 1)];dummy1[0] = dummy2 + w;for (int i = 1; i <= 2 * h + 1; i++) {dummy1[i] = dummy1[i - 1] + 2 * w + 1;}double **a = dummy1 + h;}template<class T> vector<T> ruiv(vector<T> &a) {vector<T> res(a.size() + 1);rep(i, a.size())res[i + 1] = res[i] + a[i];return res;}template<class T> vector<T> ruim(vector<T> &a) {vector<T> res(a.size() + 1, 1);rep(i, a.size())res[i + 1] = res[i] * a[i];return res;}//右から左にかけての半開区間 (-1 n-1]template<class T> T *rrui(vector<T> &a) {int len = a.size();T *body = (T *) malloc((len + 1) * sizeof(T));T *res = body + 1;rer(i, len - 1)res[i - 1] = res[i] + a[i];return res;}//掛け算template<class T> T *rruim(vector<T> &a) {int len = a.size();T *body = (T *) malloc((len + 1) * sizeof(T));T *res = body + 1;res[len - 1] = 1;rer(i, len - 1)res[i - 1] = res[i] * a[i];return res;}template<class T> void plus(vector<T> &a, T v = 1) { for (auto &&u :a)u += v; }template<class T> void minu(vector<T> &a, T v = 1) { for (auto &&u :a)u -= v; }template<class T> void minus(vector<T> &a, T v = 1) { for (auto &&u :a)u -= v; }inline bool inside(int y, int x, int H, int W) { return y >= 0 && x >= 0 && y < H && x < W; }ll u(ll a) { return a < 0 ? 0 : a; }#define MIN(a) numeric_limits<a>::min()#define MAX(a) numeric_limits<a>::max()template<class T> T min(vector<vector<T>> &a) {T res = MAX(T);rep(i, a.size())chmin(res, *min_element(all(a[i])));return res;}template<class T> T max(vector<vector<T>> &a) {T res = MIN(T);rep(i, a.size())chmax(res, *max_element(all(a[i])));return res;}bool bget(ll m, int keta) { return (m >> keta) & 1; }int bget(ll m, int keta, int sinsuu) {m /= (ll) pow(sinsuu, keta);return m % sinsuu;}inline ll bit(int n) { return (1LL << (n)); }inline ll bit(int n, int sinsuu) { return (ll) pow(sinsuu, n); }int bcou(ll m) { return __builtin_popcount(m & 0xFFFFFFFF) + __builtin_popcount(m >> 32); }//初期化は0を渡すll nextComb(ll &mask, int n, int r) {if (!mask)return mask = (1LL << r) - 1;ll x = mask & -mask; //最下位の1ll y = mask + x; //連続した下の1を繰り上がらせるll res = ((mask & ~y) / x >> 1) | y;if (bget(res, n))return mask = 0;else return mask = res;}//n桁以下でビットがr個立っているもののvectorを返すvl bitCombList(int n, int r) {vl res;int m = 0;while (nextComb(m, n, r)) {res.pb(m);}return res;}//大文字小文字を区別するint altoiaZ(char c) {if ('A' <= c && c <= 'Z')return c - 'A';return c - 'a' + 26;}char itoalaZ(int i) {if (i < 26)return 'A' + i;return 'a' + i - 26;}//aもAも0を返す 基本小文字int altoi(char c) {if ('A' <= c && c <= 'Z')return c - 'A';return c - 'a';}char itoal(int i) {return 'a' + i;}int ctoi(char c) { return c - '0'; }#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );void compress(vi &a) {vi b;int len = a.size();for (int i = 0; i < len; ++i) {b.push_back(a[i]);}sort(b);UNIQUE(b);for (int i = 0; i < len; ++i) {a[i] = lower_bound(all(b), a[i]) - b.begin();}}void compress(int a[], int len) {vi b;for (int i = 0; i < len; ++i) {b.push_back(a[i]);}sort(b);UNIQUE(b);for (int i = 0; i < len; ++i) {a[i] = lower_bound(all(b), a[i]) - b.begin();}}//要素が見つからなかったときに困る#define binarySearch(a, v) (binary_search(all(a),v))#define lowerIndex(a, v) (lower_bound(all(a),v)-a.begin())#define lowerBound(a, v) (*lower_bound(all(a),v))#define upperIndex(a, v) (upper_bound(all(a),v)-a.begin())#define upperBound(a, v) (*upper_bound(all(a),v))#define ans(a) cout<<a<<endl;continue;#define poll(a) q.front();q.pop()#define dpoll(a) q.front();q.pop_front()#define pollLast(a) q.back();q.pop_back()#define pollBack(a) q.back();q.pop_back()template<class T> inline void fin(T s) { cout << s << endl, exit(0); }template<class T> struct edge {int from, to;T cost;int id;int type;edge(int f, int t, T c = 1, int id = -1, int ty = -1) : from(f), to(t), cost(c), id(id), type(ty) {}bool operator<(const edge &b) const { return cost < b.cost; }bool operator>(const edge &b) const { return cost > b.cost; }};template<typename T> class graph {protected:vector<bool> _used;public :vector<vector<edge<T>>> g;vector<edge<T>> edges;int n, root = -1;graph(int n) : n(n) { g.resize(n), _used.resize(n); }void clear() { g.clear(), edges.clear(); }void resize(int n) {this->n = n;g.resize(n);_used.resize(n);}int size() { return g.size(); }bool isleaf(int v) {assert(root != -1);return g[v].size() == 1 && g[v][0].from != root;}vector<edge<T> > &operator[](int i) { return g[i]; }virtual void add(int from, int to, T cost, int ty) = 0;virtual bool used(edge<T> &e) = 0;virtual bool used(int id) = 0;virtual void del(edge<T> &e) = 0;virtual void del(int id) = 0;};template<class T=int> class undigraph : public graph<T> {public:using graph<T>::g;using graph<T>::n;using graph<T>::edges;using graph<T>::_used;undigraph(int n) : graph<T>(n) {}void add(int f, int t, T cost = 1, int ty = -1) {if (!(0 <= f && f < n && 0 <= t && t < n))ole();int id = edges.size();g[f].emplace_back(f, t, cost, id, ty);g[t].emplace_back(t, f, cost, id + 1, ty);edges.emplace_back(f, t, cost, id, ty);edges.emplace_back(t, f, cost, id + 1, ty);}void add(edge<T> &e) {int f = e.from, t = e.to, ty = e.type;T cost = e.cost;add(f, t, cost, ty);}bool used(edge<T> &e) { return _used[e.id]; }bool used(int id) { return _used[id]; }void del(edge<T> &e) { _used[e.id] = _used[e.id ^ 1] = 1; }void del(int id) { _used[id] = _used[id ^ 1] = 1; }};template<typename T =ll> class digraph : public graph<T> {public:using graph<T>::g;using graph<T>::n;using graph<T>::edges;using graph<T>::_used;digraph(int n) : graph<T>(n) {}void add(int f, int t, T cost = 1, int ty = -1) {if (!(0 <= f && f < n && 0 <= t && t < n))ole();int id = edges.size();g[f].emplace_back(f, t, cost, ty, id);edges.emplace_back(f, t, cost, ty, id);}bool used(edge<T> &e) { return _used[e.id]; }bool used(int id) { return _used[id]; }void del(edge<T> &e) { _used[e.id] = _used[e.id ^ 1] = 1; }void del(int id) { _used[id] = _used[id ^ 1] = 1; }};template<class T> bool nibu(const graph<T> &g) {UnionFind uf(g.n * 2);for (auto &&e :g.edges)uf.unite(e.f, e.t + g.n), uf.unite(e.f + g.n, e.t);return !uf.same(0, g.n);}template<class T> vector<T> &dijkstra(const graph<T> &g, int s) {if (!(0 <= s && s < g.n))ole();T initValue = MAX(T);vector<T> dis(g.n, initValue);priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> q;dis[s] = 0;q.emplace(0, s);while (q.size()) {T nowc = q.top().F;int i = q.top().S;q.pop();if (dis[i] != nowc)continue;for (auto &&e : g.g[i]) {int to = e.to;T cost = nowc + e.cost;if (dis[to] > cost) {dis[to] = cost;q.emplace(dis[to], to);}}}//たどり着かないなら-1for (auto &&d :dis) if (d == initValue)d = -1;return dis;}//機能拡張template<typename T> void remove(vector<T> &v, unsigned int i) { v.erase(v.begin() + i); }template<typename T> void remove(vector<T> &v, unsigned int s, unsigned int e) {v.erase(v.begin() + s, v.begin() + e);}template<typename T> void removen(vector<T> &v, unsigned int s, unsigned int n) {v.erase(v.begin() + s, v.begin() + s + n);}template<typename T> void erase(vector<T> &v, unsigned int i) { v.erase(v.begin() + i); }template<typename T> void erase(vector<T> &v, unsigned int s, unsigned int e) {v.erase(v.begin() + s, v.begin() + e);}template<typename T> void erasen(vector<T> &v, unsigned int s, unsigned int n) {v.erase(v.begin() + s, v.begin() + s + n);}template<typename T> void insert(vector<T> &v, unsigned int i, T t) { v.insert(v.begin() + i, t); }template<typename T> void insert(vector<T> &v, unsigned int i, vector<T> list) {for (auto &&va :list)v.insert(v.begin() + i++, va);}template<typename T> void insert(vector<T> &v, unsigned int i, initializer_list<T> list) {for (auto &&va :list)v.insert(v.begin() + i++, va);}template<typename T> void insert(set<T> &v, vector<T> list) {for (auto &&va :list)v.insert(va);}template<typename T> void insert(set<T> &v, initializer_list<T> list) {for (auto &&va :list)v.insert(va);}int mod(int a, int m) {return (a % m + m) % m;}ll ma = numeric_limits<ll>::min();ll mi = numeric_limits<ll>::max();//閉路がなければtruebool topo(vi &res, digraph<int> &g) {int n = g.g.size();vi nyu(n);rep(i, n)for (auto &&e :g[i])nyu[e.to]++;queue<int> st;rep(i, n)if (nyu[i] == 0)st.push(i);while (st.size()) {int v = st.front();st.pop();res.pb(v);fora(e, g[v]) if (--nyu[e.to] == 0)st.push(e.to);}return res.size() == n;}//辞書順最小トポロジカルソートbool topos(vi &res, digraph<int> &g) {int n = g.g.size();vi nyu(n);rep(i, n)for (auto &&e :g[i])nyu[e.to]++;//小さい順priority_queue<int, vector<int>, greater<int> > q;rep(i, n)if (nyu[i] == 0)q.push(i);while (q.size()) {int i = q.top();q.pop();res.pb(i);fora(e, g[i])if (--nyu[e.to] == 0)q.push(e.to);}return res.size() == n;}vector<string> split(const string a, const char deli) {string b = a + deli;int l = 0, r = 0, n = b.size();vector<string> res;rep(i, n) {if (b[i] == deli) {r = i;if (l < r)res.push_back(b.substr(l, r - l));l = i + 1;}}return res;}vector<string> split(const string a, const string deli) {string b = a + deli;int l = 0, r = 0, n = b.size(), dn = deli.size();vector<string> res;rep(i, n) {if (i + dn <= n && b.substr(i, i + dn) == deli) {r = i;if (l < r)res.push_back(b.substr(l, r - l));i += dn - 1;l = i + 1;}}return res;}int n, k, m, h, w, x, y, q;int cou;vi a, b, c;undigraph<> g(2 * k5);int dp[2020][2020][2];//黒の数 黒mint sub[2020][2];//黒の数 黒int ns[2020];void ds(int i, int p) {forg(gi, g[i])if (t != p)ds(t, i);int sum = 1;dp[i][0][0] = 1;dp[i][1][1] = 1;if (g[i].size())forg(gi, g[i]) {if (t == p)continue;rep(ni, sum + 1) {rep(nt, ns[t] + 1) {rep(bi, 2) {rep(bt, 2) {if (dp[i][ni][bi] < 0 || dp[t][nt][bt] < 0)continue;//黒白は無理if (bi && !bt)continue;sub[ni + nt][bi] += dp[i][ni][bi] * dp[t][nt][bt];}}}}sum += ns[t];rep(s, sum + 1)rep(b, 2) {dp[i][s][b] = sub[s][b];sub[s][b] = 0;}}ns[i] = sum;}signed main() {cin >> n >> k;rep(i, n - 1) {int f, s;cin >> f >> s;g.add(f, s);}fill(dp, -1);fill(sub, 0);setMod();ds(0, -1);cout << dp[0][k][0] + dp[0][k][1] << endl;return 0;}