Advertisement
Guest User

Untitled

a guest
Mar 11th, 2012
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <set>
  5. #include <utility>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. const int MAXN = 50100;
  10. const int MAXK = 501;
  11.  
  12. int n, k;
  13. vector<int> v[MAXN];
  14. int a, b;
  15.  
  16. long long dp[MAXN][MAXK];
  17. int p[MAXN];
  18. bool vis[MAXN];
  19.  
  20. long long res;
  21.  
  22. void go(int u, int anc = -1) {
  23.     vis[u] = true;
  24.     p[u] = anc;
  25.     for (int i = 0; i < (int)v[u].size(); i++) {
  26.         if (!vis[v[u][i]]) {
  27.             go(v[u][i], u);
  28.             for (int j = 0; j < k; j++) {
  29.                 dp[u][j + 1] += dp[v[u][i]][j];
  30.             }
  31.         }
  32.     }  
  33.     dp[u][0] = 1;
  34.     return;
  35. }
  36.  
  37. long long calc(int u) {
  38.     long long ans = 0;
  39.     for (int i = 0; i < (int)v[u].size(); i++) {
  40.         if (v[u][i] == p[u])
  41.             continue;
  42.            
  43.         for (int j = 1; j < k; j++) {
  44.             ans += dp[v[u][i]][j - 1] * (dp[u][k - j] - dp[v[u][i]][k - j - 1]);
  45.         }
  46.     }
  47.     //cerr << dp[u][k] << " ";
  48.     ans >>= 1; 
  49.     return (ans + dp[u][k]);
  50. }
  51.  
  52. int main() {
  53.     //freopen("input.txt", "r", stdin);
  54.     //freopen("output.txt", "w", stdout);
  55.     scanf("%d%d", &n, &k);
  56.     for (int i = 0; i < n - 1; i++) {
  57.         scanf("%d%d", &a, &b);
  58.         a--, b--;
  59.         v[a].push_back(b);
  60.         v[b].push_back(a); 
  61.     }  
  62.    
  63.     go(0);
  64.     for (int i = 0; i < n; i++) {
  65.         //cerr << calc(i) << " ";
  66.         res += calc(i);
  67.     }
  68.     cout << res << endl;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement