A8394. Distance in Tree

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.
树是不包含任何循环的连通图。

树的两个顶点之间的距离是这两个顶点之间最短路径的长度(以边为单位)。

给你一棵有 n 个顶点和一个正数 k 的树。请找出顶点之间距离恰好为 k 的不同顶点对的数目。请注意，( v ， u )和( u ， v )被视为同一对。

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.
第一行包含两个整数 n 和 k ( 1 ≤ n ≤ 50000 , 1 ≤ k ≤ 500 )--顶点数和顶点之间的所需距离。
接下来的 n - 1 行将边描述为" ai "。 bi "(不带引号)( 1 ≤ ai, bi ≤ n ， ai ≠ bi )，其中 ai 和 bi 是由第 i 条边连接的顶点。所有给定的边都是不同的。

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.
打印一个整数 - 树顶点之间距离正好为 k 的不同顶点对的数目。
请不要使用 %lld 指定符读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d指定符。

In the first sample the pairs of vertexes at distance 2 from each other are (1, 3), (1, 5), (3, 5) and (2, 4).
在第一个样本中，相距 2 的顶点对分别是 (1, 3)、(1, 5)、(3, 5) 和 (2, 4)。