Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define sl(n) scanf("%lld", &n)
- #define sf(n) scanf("%lf", &n)
- #define si(n) scanf("%d", &n)
- #define ss(n) scanf("%s", n)
- #define pii pair <int, int>
- #define pll pair <ll, ll>
- #define plp pair <int, pll >
- #define pb push_back
- #define fr first
- #define sc second
- vector <ll> ed[300], tree[300];
- ll dn[300], rt[300];
- void gdfs(ll n, ll par, ll take, ll right)
- {
- // cout << "gdfs " << n << " " << par << " " << take << endl;
- if (take)
- dn[par] = n;
- if (right != -1)
- rt[n] = right;
- ll cn = 0;
- for (ll i = 0; i < ed[n].size(); i++)
- {
- ll v = ed[n][i];
- if (v != par)
- gdfs(v, n, cn==0?1:0, (i<ed[n].size()-1?ed[n][i+1]:-1));
- if (v != par)
- cn++;
- }
- }
- bool vis[210][210][2][2];
- ll dp[210][210][2][2];
- ll mod = 1000000007;
- ll dfs(ll n, ll rem, ll pok, ll par)
- {
- // cout << n << " beg " << rem << " " << ok << " " << vis[n][rem][ok] << endl;
- if (n == 201)
- {
- if (rem == 0 && pok == 1)
- return 1;
- return 0;
- }
- if (rem == 0)
- return (pok == 1);
- ll &ret = dp[n][rem][pok][par];
- if (vis[n][rem][pok][par])
- return ret;
- vis[n][rem][pok][par] = 1;
- ret = 0;
- ll down = dn[n], right = rt[n], rm;
- if (right != 0)
- {
- rm = rem - 1;
- for (ll i = 0; i <= rm; i++)
- {
- ll x = dfs(down, i, par==1?1:0, 1);
- ll y = dfs(right, rm-i, 1, par);
- ret = (ret + ((x*y)%mod))%mod;
- }
- rm = rem;
- for (ll i = 0; i <= rm; i++)
- {
- ll x = dfs(down, i, 1, 0);
- ll y = dfs(right, rm-i, pok, par);
- ret = (ret + ((x*y)%mod))%mod;
- }
- }
- else
- {
- ret = (ret + dfs(down, rem-1, par==1?1:0, 1))%mod;
- if (pok == 1)
- ret = (ret + dfs(down, rem, 1, 0))%mod;
- }
- // cout << n << " " << rem << " " << pok << " " << par << " " << ret << endl;
- return ret;
- }
- int main ()
- {
- // freopen("inl.txt", "r", stdin);
- // freopen("outu.txt", "w", stdout);
- // ios_base::sync_with_stdio(0); // no printf/scanf must be present
- ll cs, t, i, j, k, x, y, z, ans, q, m, n;
- for (cs = 1; sl(n)!=EOF; cs++)
- {
- sl(k);
- for (i = 1; i <= n; i++)
- {
- ed[i].clear();
- tree[i].clear();
- dn[i] = 201;
- rt[i] = 0;
- }
- for (i = 1; i < n; i++)
- {
- sl(x);
- sl(y);
- ed[x].pb(y);
- ed[y].pb(x);
- }
- gdfs(1, 0, 1, -1);
- memset(vis, 0, sizeof(vis));
- printf("%lld\n", dfs(1, k, 1, 0));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement