Prune and Sprout

You are given a rooted tree whose vertices are labeled $1,2,\ldots,n$, with vertex $1$ as the root. The labels of the original vertices are permanent.

A leaf is a vertex with no children. You may perform any number of the following operations:

1. Delete every leaf except the root.
2. Attach one new vertex as a child of every current leaf.

New vertices are unlabeled. A new vertex created below a particular leaf is distinguished by its position in the rooted tree. Thus, configurations containing different sets of original labeled vertices are considered different, even when their underlying unlabeled rooted trees are isomorphic.

Two configurations are considered equal precisely when there is a root-preserving isomorphism between them that fixes every surviving original labeled vertex.

Determine the number of distinct configurations with exactly $k$ vertices that are reachable from the initial tree.

The first line contains two integers $n$ and $k$. ($1 \le n, k \le 300\,000$)

Each of the next $n-1$ lines contains two integers $u$ and $v$, indicating that the vertex $u$ and the vertex $v$ are connected by an edge. ($1 \le u, v \le n$; $u \ne v$)

The input always describes a rooted tree with root $1$.

Print one integer: the number of distinct reachable configurations containing exactly $k$ vertices.