Salvens

G

Aug 3rd, 2023
876
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <vector>
  4. #include <array>
  5. #include <set>
  6.  
  7. using namespace std;
  8.  
  9. //#define int long long
  10.  
  11. const long long INF = 1e9 + 7;
  12. const int MAXN = 5e4 + 100;
  13. const int N = 1e5 + 10;
  14. const int MOD = 1e9 + 7;
  15.  
  16. int n, k;
  17. int dp[MAXN][510];
  18. array<vector<int>, MAXN> g;
  19. int ans = 0;
  20.  
  21. void dfs(int v, int p) {
  22.     dp[v][0] = 1;
  23.     for (auto to: g[v]) {
  24.         if (to == p) {
  25.             continue;
  26.         }
  27.         dfs(to, v);
  28.         for (int len = 0; len < k; ++len) {
  29.             ans += dp[to][len] * dp[v][k - len - 1];
  30.         }
  31.         for (int len = 0; len <= k; ++len) {
  32.             dp[v][len + 1] += dp[to][len];
  33.         }
  34.     }
  35. }
  36.  
  37. signed main() {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(nullptr);
  40.     cout.tie(nullptr);
  41.     cin >> n >> k;
  42.     for (int i = 0; i < n - 1; ++i) {
  43.         int u, v;
  44.         cin >> u >> v;
  45.         --u, --v;
  46.         g[u].emplace_back(v);
  47.         g[v].emplace_back(u);
  48.     }
  49.     dfs(0, -1);
  50.     cout << ans << '\n';
  51. }
Advertisement
Add Comment
Please, Sign In to add comment