fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 1e5 + 5,MaxK = 1e2 + 5;
  5.  
  6. long long n,k,dp[MaxN][MaxK][2];
  7. vector<long long> a[MaxN];
  8.  
  9. // 0 là điểm cuối
  10. // 1 là điểm nối
  11. void dfs(long long u, long long par)
  12. {
  13.     dp[u][0][0]=1;
  14.  
  15.     for (long long v : a[u])
  16.     {
  17.         if(v==par) continue;
  18.  
  19.         dfs(v,u);
  20.  
  21.         for (long long t=0; t<=k-2; t++)
  22.         {
  23.             dp[u][k][1]+=dp[v][t][0]*dp[u][k-1-t][0];
  24.         }
  25.  
  26.         for (long long i=1; i<=k; i++)
  27.         {
  28.             dp[u][i][0]+=dp[v][i-1][0];
  29.         }
  30.     }
  31. }
  32.  
  33. void input()
  34. {
  35.     cin >> n >> k;
  36.  
  37.     for (long long i=1; i<n; i++)
  38.     {
  39.         long long u,v;
  40.         cin >> u >> v;
  41.  
  42.         a[u].push_back(v);
  43.         a[v].push_back(u);
  44.     }
  45. }
  46.  
  47. void solve()
  48. {
  49.     dfs(1,-1);
  50.  
  51.     long long ans=0;
  52.  
  53.     for (long long i=1; i<=n; i++)
  54.     {
  55.         ans+=dp[i][k][0];
  56.         ans+=dp[i][k][1];
  57.     }
  58.  
  59.     cout << ans;
  60. }
  61.  
  62. int main()
  63. {
  64.     ios_base::sync_with_stdio(0);
  65.     cin.tie(0);
  66.  
  67.     input();
  68.     solve();
  69. }
  70.  
Success #stdin #stdout 0.01s 7376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Akj5fF
language:
C++14 (gcc 8.3)
created:
2 days 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!