D. Distance in Tree

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=5e4+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair<int,int>
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11 #define ull unsigned long long
12 ll ans;
13 ll dp[maxn][505];
14 int n,k;
15 vector<int>E[maxn];
16 
17 
18 void dfs(int u,int fa)
19 {
20     dp[u][0]=1;
21     for(auto &v:E[u])
22     {
23         if(v==fa) continue;
24         dfs(v,u);
25         for(int i=0;i<k;i++)
26             ans+=dp[v][k-1-i]*dp[u][i];
27         for(int i=1;i<=k;i++)
28             dp[u][i]+=dp[v][i-1];
29     }
30 }
31 
32 int main()
33 {
34     ios::sync_with_stdio(0);
35     cin.tie(0);
36     cin>>n>>k;
37     for(int i=1;i<n;i++)
38     {
39         int x,y;
40         cin>>x>>y;
41         E[x].pb(y);
42         E[y].pb(x);
43     }
44     dfs(1,0);
45     cout<<ans<<‘\n‘;
46 
47 
48 
49 
50 }