fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 1e5;
  9. const int maxk = 5;
  10. const int maxlog = 16;
  11. const int MOD = 1e9 + 7;
  12.  
  13. int n, k;
  14. vector<int> adj[maxn + 10], a;
  15. ll dp[maxn + 10][maxlog + 5][2], f[maxn + 10][maxlog + 10][maxk + 10], ans = 0;
  16.  
  17. void dfs(int top, int p = -1)
  18. {
  19.     for (int next_top : adj[top])
  20.         if (next_top != p)
  21.             dfs(next_top, top);
  22.     a.clear();
  23.     for (int next_top : adj[top])
  24.     {
  25.         if (next_top == p)
  26.             continue;
  27.         a.push_back(next_top);
  28.         for (int mx = 0; mx <= maxlog; mx++)
  29.             for (int cnt = 0; cnt <= k; cnt++)
  30.                 f[a.size()][mx][cnt] = 0;
  31.     }
  32.  
  33. //    if (a.size() == 0 && top != 1)
  34. //        dp[top][0][0] = dp[top][1][1] = 1;
  35.  
  36.     f[0][0][0] = 1;
  37.     for (int i = 0; i < a.size(); i++)
  38.         for (int mx = 0; mx <= maxlog; mx++)
  39.             for (int cnt = 0; cnt <= k; cnt++)
  40.                 for (int new_mx = 0; new_mx <= maxlog; new_mx++)
  41.                 {
  42.                     (f[i + 1][max(mx, new_mx + 1)][cnt] += f[i][mx][cnt] * dp[a[i]][new_mx][0] % MOD) %= MOD;
  43.                     (f[i + 1][max(mx, new_mx)][cnt + 1] += f[i][mx][cnt] * dp[a[i]][new_mx][1] % MOD) %= MOD;
  44.                 }
  45.     for (int mx = 0; mx <= maxlog; mx++)
  46.     {
  47.         for (int i = 0; i <= k; i++)
  48.             (dp[top][mx][0] += f[a.size()][mx][i]) %= MOD;
  49.         for (int i = 0; i < k; i++)
  50.             (dp[top][mx][1] += f[a.size()][mx][i]) %= MOD;
  51.     }
  52. //    cout << top, el;
  53. //    for (int i = 0; i <= 5; i++)
  54. //        cout << dp[top][i][0] << ' ' << dp[top][i][1], el;
  55. //    for (int i = 0; i <= 5; i++)
  56. //        cout << f[a.size()][i][0] << ' ' << f[a.size()][i][1] << ' ' << dp[top][i][0] << ' ' << dp[top][i][1], el;
  57. }
  58.  
  59. int main()
  60. {
  61.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  62.     if (fopen("SPEEDUP.INP", "r"))
  63.     {
  64.         freopen("SPEEDUP.INP", "r", stdin);
  65.         freopen("SPEEDUP.OUT", "w", stdout);
  66.     }
  67.  
  68.     cin >> n >> k;
  69.     for (int i = 1; i < n; i++)
  70.     {
  71.         int x, y;
  72.         cin >> x >> y;
  73.         adj[x].push_back(y);
  74.         adj[y].push_back(x);
  75.     }
  76.     dfs(1);
  77.     for (int i = 0; i <= __lg(n); i++)
  78.         (ans += dp[1][i][0]) %= MOD;
  79.     cout << ans;
  80. }
Success #stdin #stdout 0.01s 6000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/6fYdgu
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!