Codeforces 161D Distance in Tree(树型DP)

$k <= 500$ 这个条件十分重要。

设$f[i][j]$为以$i$为子树，所有后代中相对深度为$j$的结点个数。

状态转移的时候，一个结点的信息由他的儿子转移过来。

那么一边进行状态转移，一边统计答案即可。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int f[50010][503], deep[50010];
 6 vector <int> v[50010];
 7 int n, k, x, y;
 8 long long ans;
 9 
10 void dfs(int x, int fa, int dep){
11     int c[510];
12     deep[x] = dep;
13     for (auto u : v[x]){
14         if (u == fa) continue;
15         dfs(u, x, dep + 1); 
16         memset(c, 0, sizeof c); c[1] = 1;
17         for (int i = 1; i <= k; ++i) c[i + 1] = f[u][i]; 
18         for (int i = 1; i <= k - 1; ++i) ans += (long long)f[x][i] * c[k - i];
19         for (int i = 1; i <= k; ++i) f[x][i] += c[i];
20     }
21 }
22 
23 
24 int main(){
25     
26     ans = 0;
27     scanf("%d%d", &n, &k);
28     for (int i = 1; i <= n - 1; ++i){
29         scanf("%d%d", &x, &y);
30         v[x].push_back(y);
31         v[y].push_back(x);
32     }
33 
34     memset(deep, 0, sizeof deep);
35     dfs(1, 0, 0);
36     for (int i = 1; i <= n; ++i) if (deep[i] >= k) ++ans;
37     printf("%lld
", ans);
38 
39 
40     return 0;
41 
42 }