一棵树，边长都是1，问这棵树有多少点对的距离刚好为k
令tree(i)表示以i为根的子树
dp[i][j][1]:在tree（i）中，经过节点i，长度为j，其中一个端点为i的路径的个数
dp[i][j][0]:在tree(i)中，经过节点i，长度为j，端点不在i的路径的个数
则目标：∑(dp[i][k][0]+dp[i][k][1])
初始化：dp[i][0][1]=1,其余为0
siz[i]:tree(i)中，i与离i最远的点的距离
递推：
dp[i][j][0]+=dp[i][j-l][1]*dp[soni][l-1][1]
dp[i][j][1]=∑dp[soni][j-1][1]
注意：在更新每一个dp[i]时，先更新dp[i][j][0],再更新dp[i][j][1]
#include<cstdio>
#include<cstring>
#include<iostream> using namespace std; const int maxn=+;
const int maxk=;
#define LL long long inline int max(int a,int b)
{
return a>b?a:b;
} inline int min(int a,int b)
{
return a<b?a:b;
} LL dp[maxn][maxk][];
int siz[maxn];
struct Edge
{
int to,next;
};
Edge edge[maxn<<];
int head[maxn];
int tot;
int k; void init()
{
memset(head,-,sizeof head);
tot=;
memset(dp,,sizeof dp);
} void addedge(int u,int v)
{
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
} void solve(int ,int );
void dfs(int ,int ); int main()
{
init();
int n;
scanf("%d %d",&n,&k);
for(int i=;i<n;i++)
{
int u,v;
scanf("%d %d",&u,&v);
addedge(u,v);
addedge(v,u);
}
solve(n,k);
return ;
} void solve(int n,int k)
{
dfs(,);
LL ans=;
for(int i=;i<=n;i++)
{
ans+=(dp[i][k][]+dp[i][k][]);
}
cout<<ans<<endl;
return ;
} void dfs(int u,int pre)
{
dp[u][][]=;
siz[u]=;
for(int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(v==pre)
continue;
dfs(v,u);
for(int l=;l<=siz[v]+;l++)
{
for(int j=l+;j<=siz[u]+l;j++)
{
if(j>k)
continue;
dp[u][j][]+=dp[u][j-l][]*dp[v][l-][];
}
}
for(int j=;j<=siz[v]+;j++)
dp[u][j][]+=dp[v][j-][];
siz[u]=max(siz[u],siz[v]+);
siz[u]=min(siz[u],k);
}
}