fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <utility>
  10. #include <math.h>
  11. #include <cstdlib>
  12. #include <memory.h>
  13. #include <queue>
  14. #include <assert.h>
  15. #include <cmath>
  16.  
  17. using namespace std;
  18.  
  19. #define pb push_back
  20. #define f first
  21. #define s second
  22. #define mp make_pair 
  23. #define sz(A) ((int)(A).size())
  24. #define forn(i, n) for (int i = 0; i < int(n); i++)
  25. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  26. #define foran(i, a, n) for (int i = int(a); i < int(n); i++)
  27. #define y1 gftxdtrtfhyjfctrxujkvbhyjice
  28. #define y0 ehfoiuvhefroerferjhfjkehfjke
  29.  
  30. typedef long long ll;
  31. typedef unsigned long long ull;
  32. typedef pair <int,int> pii;
  33.  
  34. const double EPS = 1e-9;
  35. const int MAXN = 70;
  36.  
  37. vector <int> g[MAXN];
  38. int max_depth[MAXN];
  39. int max_diam[MAXN];
  40. ll ans[MAXN][MAXN][MAXN];//vertex, diameter, max_depth
  41. ll dp[MAXN][MAXN][MAXN];//pos, diameter, max_depth
  42. int n, k;
  43. ll res;
  44.  
  45. void dfs (int v, int p = -1) {
  46.   forn(i, sz(g[v])) {
  47.     int to = g[v][i];
  48.  
  49.     if  (to == p)
  50.       continue;
  51.  
  52.     dfs(to, v);
  53.   }
  54.  
  55.   memset (dp, 0, sizeof dp);
  56.   dp[0][0][0] = 1ll;
  57.   max_diam[v] = 0;
  58.   int max_depth1 = 0, max_depth2 = 0;
  59.  
  60.   for (int i = 0; i < sz(g[v]); i++) 
  61.   {
  62.     int to = g[v][i];
  63.  
  64.     for (int diam = 0; diam <= max_diam[v]; diam++)
  65.       for (int de = 0; de <= max_depth[v]; de++) 
  66.       {
  67.         dp[i + 1][diam][de] += dp[i][diam][de];
  68.  
  69.         if  (to == p)
  70.           continue;
  71.  
  72.         for (int cdiam = 0; cdiam <= max_diam[to]; cdiam++)
  73.           for (int cde = 0; cde <= max_depth[to]; cde++) {
  74.             int ndiam = max(max(cdiam, diam), cde + 1 + de);
  75.             int nde = max(cde + 1, de);
  76.             dp[i + 1][ndiam][nde] += dp[i][diam][de] * ans[to][cdiam][cde];
  77.           }
  78.       }
  79.  
  80.     if  (to != p) {
  81.       if  (max_depth1 < max_depth[to] + 1) {
  82.         max_depth2 = max_depth1;
  83.         max_depth1 = max_depth[to] + 1;
  84.       } else if  (max_depth2 < max_depth[to] + 1)
  85.         max_depth2 = max_depth[to] + 1;
  86.  
  87.       max_diam[v] = max_depth1 + max_depth2;
  88.       max_depth[v] = max_depth1;
  89.     }
  90.   }
  91.  
  92.   for (int diam = 0; diam <= max_diam[v]; diam++)
  93.     for (int de = 0; de <= max_depth[v]; de++) {
  94.       ans[v][diam][de] = dp[sz(g[v])][diam][de];
  95.       if  (diam <= k)
  96.         res += ans[v][diam][de];
  97.     }      
  98. }
  99.  
  100. int main() {
  101.   int t; scanf("%d", &t);
  102.   while (t--) {
  103.     scanf("%d %d", &n, &k);
  104.     forn(i, n)
  105.       g[i].clear();
  106.  
  107.     forn(i, n - 1) {
  108.       int a, b; scanf("%d %d", &a, &b);
  109.       g[a].pb(b); g[b].pb(a);
  110.     }
  111.  
  112.     res = 0;
  113.     dfs(0);
  114.  
  115.     printf("%I64d\n", res);
  116.   }
  117.  
  118.   return 0;
  119. }
Success #stdin #stdout 0s 8352KB
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/4mBo1w
language:
C++ (gcc 8.3)
created:
11 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!