August 20. Kiev Summer school
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.
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 (1 ≤
bi ≤ n,
bi 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.
5 2 1 2 2 3 3 4 2 5