- All Contests
- HourRank 16
- Jenny's Subtrees

# Jenny's Subtrees

# Jenny's Subtrees

Jenny loves experimenting with trees. Her favorite tree has nodes connected by edges, and each edge is unit in length. She wants to cut a *subtree* (i.e., a connected part of the original tree) of radius from this tree by performing the following two steps:

- Choose a node, , from the tree.
- Cut a subtree consisting of
*all*nodes which are*not further*than units from node .

For example, the blue nodes in the diagram below depict a subtree centered at that has radius :

Given , , and the definition of Jenny's tree, find and print the number of *different* subtrees she can cut out. Two subtrees are considered to be different if they are not isomorphic.

**Input Format**

The first line contains two space-separated integers denoting the respective values of and .

Each of the next subsequent lines contains two space-separated integers, and , describing a bidirectional edge in Jenny's tree having length .

**Constraints**

**Subtasks**

For of the max score:

**Output Format**

Print the total number of different possible subtrees.

**Sample Input 0**

```
7 1
1 2
1 3
1 4
1 5
2 6
2 7
```

**Sample Output 0**

```
3
```

**Explanation 0**

In the diagram below, blue nodes denote the possible subtrees:

The last subtrees are considered to be the same (i.e., they all consist of two nodes connected by one edge), so we print as our answer.

**Sample Input 1**

```
7 3
1 2
2 3
3 4
4 5
5 6
6 7
```

**Sample Output 1**

```
4
```

**Explanation 1**

In the diagram below, blue nodes denote the possible subtrees:

Here, we have four possible different subtrees.