We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. All Contests
  2. HourRank 16
  3. Jenny's Subtrees

Jenny's Subtrees

Problem
Submissions
Leaderboard
Discussions
Editorial

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:

  1. Choose a node, , from the tree.
  2. 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 :

image

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:

image

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:

image

Here, we have four possible different subtrees.

Author

nikasvanidze

Difficulty

Hard

Max Score

70

Submitted By

136

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download all test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy