CF161D.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 \leq n \leq 50000$，$1 \leq k \leq 500$）—— 分别表示顶点数和所要求的顶点间距离。

接下来的 $n-1$ 行描述边，每行为“$a_i\ b_i$”（不含引号）（$1 \leq a_i,\,b_i \leq n$，$a_i \neq b_i$），其中 $a_i$ 和 $b_i$ 是第 $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$ 的不同顶点对的数量。

请注意：在 C++ 中，请勿使用 %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)$。