fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int MOD = 1e9+7;
  7. const int N = 2005;
  8.  
  9. int n, d, tin[N], tout[N], timer;
  10. vector<int> mx;
  11. vector<vector<int>> adj, P;
  12. ll ans;
  13. vector<vector<vector<ll>>> dp;
  14.  
  15. void dfs1(int u, int p) {
  16.     tin[u] = ++timer;
  17.     for (int v : adj[u]) {
  18.         if (v == p) continue;
  19.         dfs1(v, u);
  20.     }
  21.     tout[u] = timer;
  22. }
  23.  
  24. void dfs2(int u, int p) {
  25.     dp[u][0][0] = dp[u][1][0] = 1;
  26.     mx[u] = 0;
  27.     for (int v : adj[u]) {
  28.         if (v == p) continue;
  29.         dfs2(v, u);
  30.         for (int j = 3; j >= 1; j--) {
  31.             int K = min(d - 1, (j - 1) * mx[u]);
  32.             for (int k = K; k >= 0; k--) {
  33.                 if (!dp[u][j - 1][k]) continue;
  34.                 for (int len = 0; len <= mx[v]; len++) {
  35.                     int nd = len + 1;
  36.                     if (k + nd >= d) break;
  37.                     dp[u][j][k + nd] += dp[u][j - 1][k] * dp[v][1][len];
  38.                 }
  39.             }
  40.         }
  41.         mx[u] = max(mx[u], mx[v] + 1);
  42.     }
  43.  
  44.     ans += dp[u][3][d - 1];
  45.     for (int k = 0; k < d; k++) {
  46.         int r = d - k - 1;
  47.         if (r >= 0 && r < d) ans += dp[u][2][k] * P[u][r];
  48.     }
  49. }
  50.  
  51. void solve() {
  52.     cin >> n >> d;
  53.     adj.assign(n + 1, vector<int>());
  54.     for (int i = 0; i < n - 1; i++) {
  55.         int u, v; cin >> u >> v;
  56.         adj[u].push_back(v);
  57.         adj[v].push_back(u);
  58.     }
  59.  
  60.     vector<vector<int>> dist(n + 1, vector<int>(n + 1, -1));
  61.     for (int i = 1; i <= n; i++) {
  62.         dist[i][i] = 0;
  63.         queue<int> q;
  64.         q.push(i);
  65.         while (!q.empty()) {
  66.             int u = q.front(); q.pop();
  67.             for (int v : adj[u])
  68.                 if (dist[i][v] == -1) {
  69.                     dist[i][v] = dist[i][u] + 1;
  70.                     q.push(v);
  71.                 }
  72.         }
  73.     }
  74.  
  75.     timer = 0;
  76.     dfs1(1, 0);
  77.  
  78.     P.assign(n + 1, vector<int>(d, 0));
  79.     for (int u = 1; u <= n; u++)
  80.         for (int v = 1; v <= n; v++) {
  81.             if (tin[u] <= tin[v] && tin[v] <= tout[u]) continue;
  82.             int len = dist[u][v];
  83.             if (len < d) P[u][len]++;
  84.         }
  85.  
  86.     mx.assign(n + 1, 0);
  87.     dp.assign(n + 1, vector<vector<ll>>(4, vector<ll>(d, 0)));
  88.     ans = 0;
  89.     dfs2(1, 0);
  90.     cout << ans << "\n";
  91. }
  92.  
  93. int main() {
  94.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  95.  
  96.     int tests = 1; cin >> tests;
  97.     while (tests--) solve();
  98.  
  99.     #ifndef ONLINE_JUDGE
  100.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  101.     #endif
  102.  
  103.     return 0;
  104. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3
4 3
1 2
3 1
4 1
5 5
1 2
2 4
2 3
5 1
7 7
1 2
1 3
2 4
2 5
3 6
3 7
stdout
copy 
3
1
0
https://ideone.com/xRn44C
language:
C++14 (gcc 8.3)
created:
4 hours 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!