fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXN = 65;
  8.  
  9. int n, k;
  10. vector< int > e[MAXN];
  11.  
  12. long long dp[MAXN][MAXN];
  13. long long tmp[MAXN];
  14. long long sol[MAXN];
  15.  
  16. void dfs( int node, int dad ) {
  17. memset( dp[node], 0, sizeof dp[node] );
  18. dp[node][0] = 1;
  19. sol[node] = 0;
  20.  
  21. for( int i = 0; i < (int)e[node].size(); ++i ) {
  22. int w = e[node][i];
  23. if ( w == dad ) continue;
  24. dfs( w, node );
  25. memcpy( tmp, dp[node], sizeof dp[node] );
  26.  
  27. for ( int lc = 0; lc <= k; ++lc )
  28. for ( int rc = 1; rc+lc <= k; ++rc )
  29. tmp[max(lc,rc)] += dp[node][lc] * dp[w][rc-1];
  30. memcpy( dp[node], tmp, sizeof tmp );
  31. sol[node] += sol[w];
  32. }
  33.  
  34. for ( int i = 0; i <= k; ++i )
  35. sol[node] += dp[node][i];
  36. }
  37.  
  38. void process() {
  39. scanf( "%d%d", &n, &k );
  40. for ( int i = 1; i < n; ++i ) {
  41. int x, y;
  42. scanf( "%d%d", &x, &y );
  43. e[x].push_back( y );
  44. e[y].push_back( x );
  45. }
  46.  
  47. dfs( 0, -1 );
  48. printf( "%lld\n", sol[0] );
  49. }
  50.  
  51. int main() {
  52. int t; scanf( "%d", &t );
  53. for( int tt = 0; tt < t; ++tt ) {
  54. for ( int i = 0; i < MAXN; ++i ) e[i].clear();
  55. process();
  56. }
  57. }
Success #stdin #stdout 0s 2896KB
comments (?)
stdin
copy 
2
3 1
0 1
1 2
 
6 3
0 1
1 2
2 3
2 4
3 5
stdout
copy 
5
23
https://ideone.com/M8ze8h
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years 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!