A tree is a connected graph that doesn't contain any cycles.
The distance between two vertices of a tree is the length (in edges) of the shortest path between these vertices.
You are given a tree with n vertices and a positive number k. Find the number of distinct pairs of the vertices which have a distance of exactly k between them. Note that pairs (v, u) and (u, v) are considered to be the same pair.
Input
The first line contains two integers n and k (1 ≤ n ≤ 50000, 1 ≤ k ≤ 500) — the number of vertices and the required distance between the vertices.
Next n - 1 lines describe the edges as "ai bi" (without the quotes) (1 ≤ ai, bi ≤ n, ai ≠ bi), where ai and bi are the vertices connected by the i-th edge. All given edges are different.
Output
Print a single integer — the number of distinct pairs of the tree's vertices which have a distance of exactly k between them.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
Examples
5 2
1 2
2 3
3 4
2 5
4
5 3
1 2
2 3
3 4
4 5
2
题意：给定一棵树，问树上有多少个点对距离是K（K<=500）。
思路：明显的基础分治题，分别累计经过根节点的距离为K的点对。说他基础是以为既不需要排序，也不需要去重。复杂度O（NlogN*K）
（感悟：分治=若干个小分治+线性解决当前层 =NlogN。
分治=若干个小分治+logN解决当前层 =NlogN*logN。
分治=若干个小分治+K*线性解决当前层 =N*K*logN。
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int Laxt[maxn],Next[maxn],To[maxn];
int sz[maxn],son[maxn],root,cnt,N,K,ans,sn; //sn，小树的大小。
int num[],tnum[],vis[maxn];
void read(int &x){
x=; char c=getchar();
while(c>''||c<'') c=getchar();
while(c>=''&&c<='') x=(x<<)+(x<<)+c-'',c=getchar();
}
void add(int u,int v)
{
Next[++cnt]=Laxt[u];
Laxt[u]=cnt; To[cnt]=v;
}
void getroot(int u,int fa)
{
sz[u]=; son[u]=;
for(int i=Laxt[u];i;i=Next[i]){
int v=To[i];
if(v==fa||vis[v]) continue;
getroot(v,u); sz[u]+=sz[v];
son[u]=max(son[u],sz[v]);
}
son[u]=max(sz[u],sn-son[u]);
if(root==||son[root]>son[u]) root=u;
}
void getdep(int u,int fa,int dis)
{
if(K>=dis) ans+=num[K-dis],tnum[dis]++;
if(K==dis) return ;
for(int i=Laxt[u];i;i=Next[i])
if(To[i]!=fa&&!vis[To[i]])
getdep(To[i],u,dis+);
}
void dfs(int u)
{
vis[u]=;
for(int i=;i<=K;i++) num[i]=; num[]=;
for(int i=Laxt[u];i;i=Next[i]){ //暴力部分
if(vis[To[i]]) continue;
for(int j=;j<=K;j++) tnum[j]=;
getdep(To[i],,);
for(int j=;j<=K;j++) num[j]+=tnum[j];
} for(int i=Laxt[u];i;i=Next[i]){ //以大化小，分治部分
if(vis[To[i]]) continue;
sn=sz[To[i]]; root=;
getroot(To[i],u); dfs(root);
}
}
int main()
{
int u,v; scanf("%d%d",&N,&K);
for(int i=;i<N;i++){
read(u) ; read(v) ;
add(u,v); add(v,u);
}
root=; sn=N; getroot(,); dfs(root);
printf("%d\n",ans);
return ;
}