### kush_76's blog

By kush_76, history, 15 months ago, Hey everyone.. Actually i've been struggling in this tree dp question 161 Dfor about 2 days now.. I read the tutorial but wasn't able to understand it properly. The Problem goes as follows :

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 that 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.

Example Input :

5 2

1 2

2 3

3 4

2 5

Example Output :

4

By kush_76, history, 2 years ago, 