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 $(u,v)$ and $(u,v)$ are considered to be the same pair.

The first line contains two integers $ n $ and $ k $ ($ 1\le n\le50000 $, $ 1\le k\le500 $) — 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\le a_{i},b_{i}\le 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.

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.

In the first sample the pairs of vertexes at distance $2$ from each other are $(1, 3)$, $(1, 5)$, $(3, 5)$ and $(2, 4)$.