【题意】：给出一棵树，每条边的长度为1，问树上有多少点对的距离恰好为k。

【题解】：用树的分治可解，但是写起来比较麻烦。
               设状态dp[i][j]表示以i为根的子树的节点到i的距离恰为j的个数。
               然后利用乘法原理求出答案，再把儿子的信息传给父亲。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define maxn 50050
19 
20 int n, k;
21 ll dp[50050][505];
22 ll ans;
23 vector<int> vec[maxn];
24 
25 void dfs(int u, int fa) {
26     memset(dp[u], 0, sizeof(dp[u]));
27     dp[u][0] = 1;
28     int size = vec[u].size();
29     for(int i = 0; i < size; i++) {
30         int v = vec[u][i];
31         if(v == fa) continue;
32         dfs(v, u);
33         for(int j = 1; j <= k; j++) 
34             ans += dp[u][j-1] * dp[v][k-j];
35         for(int j = 1; j <= k; j++)
36             dp[u][j] += dp[v][j-1];
37     }
38 }
39 
40 int main() {
41     int u, v;
42     while(cin >> n >> k) {
43         for(int i = 0; i < maxn; i++) vec[i].clear();
44         for(int i = 1; i < n; i++) {
45             cin >> u >> v;
46             vec[u].pb(v);
47             vec[v].pb(u);
48         }
49         ans = 0;
50         dfs(1, -1);
51         cout << ans << endl;
52     }
53     return 0;
54 }
55