A - Distance in Tree

题意：给你一棵树，让你记录树上两点距离为k的点对数。
思路：
dp[i][j]代表考虑i这颗子树，与它距离为j的点数量，dp[i][0]就是1了，然后dfs处理一下就可以，那么它就是答案的一部分，还有一部分就是把i当做中转节点，从u开始递归，枚举它的每个子树，ans+=(dp[u][tt]-dp[j][tt-1])*(dp[j][k-tt-1])，最后别忘记除以二，最后有点小疑惑，为什么这样就是答案了呢，会不会重复或者漏算呢，首先dp[i][k]加起来肯定是不重复的，然后画画图发现把u当做中转的也不会有重复。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50010,M=100010;
int n,k;
int h[N],e[M],ne[M];
int dp[N][510];
ll ans;
int idx;
void add(int a,int b)
{
   
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa)
{
   
	dp[u][0]=1;
	for(int i=h[u];~i;i=ne[i])
	{
   
		int j=e[i];
		if(j==fa)
		continue;
		dfs(j,u);
		for(int t=1;t<=k;t++)
		dp[u][t]+=dp[j][t-1];
	}
	ans+=dp[u][k];
	ll tmp=0;
	for(int i=h[u];~i;i=ne[i])
	{
   
		int j=e[i];
		if(j==fa)	
		continue;
	for(int t=1;k-t-1>=0;t++)
		tmp+=(dp[u][t]-dp[j][t-1])*(dp[j][k-t-1]);
		//ans+=tmp/2;
	}
	ans+=tmp/2;
}
int main()
{
   
	cin>>n>>k;
	memset(h,-1,sizeof h);
	for(int i=0;i<n-1;i++)
	{
   
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	dfs(1,-1);
// for(int i=1;i<=n;i++)
// {
   
// for(int j=0;j<=k;j++)
// cout<<dp[i][j]<<' ';
// cout<<endl;
// }
	
	cout<<ans<<endl;
	return 0;
}