Dang_Quan_10_Tin

VOI 2020 COMNET

Jul 29th, 2021
684
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6. using ull = unsigned long long;
  7.  
  8. constexpr bool typetest = 0;
  9. constexpr int N = 1e3 + 5;
  10.  
  11. int n, k, a, b, cnt[N];
  12. ll dp[N][N][5], ans(0);
  13. vector<int> adj[N];
  14.  
  15. void Read()
  16. {
  17.     cin >> n >> k >> a >> b;
  18.     for (int i = 1; i < n; ++i)
  19.     {
  20.         int u, v;
  21.         cin >> u >> v;
  22.         adj[u].emplace_back(v);
  23.         adj[v].emplace_back(u);
  24.     }
  25. }
  26.  
  27. void dfs(int v, int p)
  28. {
  29.     dp[v][0][0] = dp[v][0][1] = 1;
  30.     cnt[v] = 1;
  31.     for (auto i : adj[v])
  32.         if (i != p)
  33.         {
  34.             dfs(i, v);
  35.             cnt[v] += cnt[i];
  36.             for (int h = k; h; --h)
  37.                 for (int l = 1; l <= h; ++l)
  38.                     for (int j = 1; j <= cnt[v]; ++j)
  39.                         for (int t = 0; t < j && t <= cnt[i]; ++t)
  40.                             dp[v][j][h] += dp[v][j - t - 1][h - l] * dp[i][t][l];
  41.  
  42.             for (int j = a; j <= b; ++j)
  43.                 ans -= dp[i][j - 1][k];
  44.         }
  45.  
  46.     for (int j = a; j <= b; ++j)
  47.         ans += dp[v][j][k];
  48.  
  49.     /*cout << v << ":\n";
  50.     for (int l = 0; l <= k; ++l)
  51.         for (int j = 0; j <= n; ++j)
  52.             cout << dp[v][j][l] << (j == n ? "\n" : " ");
  53. */
  54. }
  55.  
  56. void Solve()
  57. {
  58.     dfs(1, 1);
  59.     cout << ans;
  60. }
  61.  
  62. int32_t main()
  63. {
  64.     ios::sync_with_stdio(0);
  65.     cin.tie(0);
  66.     cout.tie(0);
  67.     int t(1);
  68.     if (typetest)
  69.         cin >> t;
  70.     for (int _ = 1; _ <= t; ++_)
  71.     {
  72.         Read();
  73.         Solve();
  74.     }
  75. }
RAW Paste Data