Distance in Tree

题意翻译

## 题目大意 输入点数为$N$一棵树 求树上长度恰好为$K$的路径个数 ## 输入格式 第一行两个数字$N,K$,如题意 接下来的$N-1$行中,每行两个整数$u,v$表示一条树边$(u,v)$ ## 输出格式 一个整数$ans$,如题意 在$Codeforces$上提交时记得用$\%I64d$哦.QwQ ## 数据范围 $1 \leq n \leq 50000$ $1 \leq k \leq 500$ 感谢@Zhang_RQ 提供的翻译

题目描述

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.

输入输出格式

输入格式

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 " $ a_{i} $ $ b_{i} $ " (without the quotes) ( $ 1<=a_{i},b_{i}<=n $ , $ a_{i}≠b_{i} $ ), where $ a_{i} $ and $ b_{i} $ are the vertices connected by the $ i $ -th edge. All given edges are different.

输出格式

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.

输入输出样例

输入样例 #1

5 2
1 2
2 3
3 4
2 5

输出样例 #1

4

输入样例 #2

5 3
1 2
2 3
3 4
4 5

输出样例 #2

2

说明

In the first sample the pairs of vertexes at distance 2 from each other are (1, 3), (1, 5), (3, 5) and (2, 4).