Need help in a tree dp problem

Revision en1, by kush_76, 2020-04-15 12:30:05

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

Please help me out on this one. Thanks in advance!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English kush_76 2020-04-15 12:30:05 1182 Initial revision (published)