Advertisement
Guest User

Untitled

a guest
Nov 21st, 2017
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.83 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define sl(n) scanf("%lld", &n)
  7. #define sf(n) scanf("%lf", &n)
  8. #define si(n) scanf("%d", &n)
  9. #define ss(n) scanf("%s", n)
  10. #define pii pair <int, int>
  11. #define pll pair <ll, ll>
  12. #define plp pair <int, pll >
  13. #define pb push_back
  14.  
  15. #define fr first
  16. #define sc second
  17.  
  18. vector <ll> ed[300], tree[300];
  19.  
  20. ll dn[300], rt[300];
  21.  
  22. void gdfs(ll n, ll par, ll take, ll right)
  23. {
  24. // cout << "gdfs " << n << " " << par << " " << take << endl;
  25.  
  26. if (take)
  27. dn[par] = n;
  28.  
  29. if (right != -1)
  30. rt[n] = right;
  31.  
  32. ll cn = 0;
  33.  
  34. for (ll i = 0; i < ed[n].size(); i++)
  35. {
  36. ll v = ed[n][i];
  37.  
  38. if (v != par)
  39. gdfs(v, n, cn==0?1:0, (i<ed[n].size()-1?ed[n][i+1]:-1));
  40.  
  41. if (v != par)
  42. cn++;
  43. }
  44. }
  45.  
  46. bool vis[210][210][2][2];
  47.  
  48. ll dp[210][210][2][2];
  49.  
  50. ll mod = 1000000007;
  51.  
  52. ll dfs(ll n, ll rem, ll pok, ll par)
  53. {
  54. // cout << n << " beg " << rem << " " << ok << " " << vis[n][rem][ok] << endl;
  55. if (n == 201)
  56. {
  57. if (rem == 0 && pok == 1)
  58. return 1;
  59. return 0;
  60. }
  61.  
  62. if (rem == 0)
  63. return (pok == 1);
  64.  
  65. ll &ret = dp[n][rem][pok][par];
  66.  
  67. if (vis[n][rem][pok][par])
  68. return ret;
  69. vis[n][rem][pok][par] = 1;
  70.  
  71. ret = 0;
  72.  
  73. ll down = dn[n], right = rt[n], rm;
  74.  
  75.  
  76. if (right != 0)
  77. {
  78. rm = rem - 1;
  79.  
  80. for (ll i = 0; i <= rm; i++)
  81. {
  82. ll x = dfs(down, i, par==1?1:0, 1);
  83. ll y = dfs(right, rm-i, 1, par);
  84.  
  85. ret = (ret + ((x*y)%mod))%mod;
  86. }
  87.  
  88. rm = rem;
  89.  
  90. for (ll i = 0; i <= rm; i++)
  91. {
  92. ll x = dfs(down, i, 1, 0);
  93. ll y = dfs(right, rm-i, pok, par);
  94.  
  95. ret = (ret + ((x*y)%mod))%mod;
  96. }
  97. }
  98. else
  99. {
  100. ret = (ret + dfs(down, rem-1, par==1?1:0, 1))%mod;
  101. if (pok == 1)
  102. ret = (ret + dfs(down, rem, 1, 0))%mod;
  103. }
  104.  
  105. // cout << n << " " << rem << " " << pok << " " << par << " " << ret << endl;
  106.  
  107. return ret;
  108. }
  109.  
  110. int main ()
  111. {
  112. // freopen("inl.txt", "r", stdin);
  113. // freopen("outu.txt", "w", stdout);
  114. // ios_base::sync_with_stdio(0); // no printf/scanf must be present
  115. ll cs, t, i, j, k, x, y, z, ans, q, m, n;
  116.  
  117. for (cs = 1; sl(n)!=EOF; cs++)
  118. {
  119. sl(k);
  120.  
  121. for (i = 1; i <= n; i++)
  122. {
  123. ed[i].clear();
  124. tree[i].clear();
  125. dn[i] = 201;
  126. rt[i] = 0;
  127. }
  128.  
  129. for (i = 1; i < n; i++)
  130. {
  131. sl(x);
  132. sl(y);
  133.  
  134. ed[x].pb(y);
  135. ed[y].pb(x);
  136. }
  137.  
  138. gdfs(1, 0, 1, -1);
  139.  
  140. memset(vis, 0, sizeof(vis));
  141.  
  142. printf("%lld\n", dfs(1, k, 1, 0));
  143. }
  144.  
  145. return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement