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
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Far Vertices

Far Vertices

Problem
Submissions
Leaderboard
Discussions
Editorial

You are given a tree that has N vertices and N-1 edges. Your task is to mark as small number of vertices as possible, such that, the maximum distance between two unmarked vertices is less than or equal to K. Output this value. Distance between two vertices i and j is defined as the minimum number of edges you have to pass in order to reach vertex i from vertex j.

Input Format
The first line of input contains two integers N and K. The next N-1 lines contain two integers (ui,vi) each, where 1 <= ui,vi <= N. Each of these lines specifies an edge.
N is no more than 100. K is less than N.

Output Format
Print an integer that denotes the result of the test.

Sample Input:

5 1  
1 2  
1 3  
1 4  
1 5

Sample Output:

3

Sample Input:

5 2  
1 2  
1 3  
1 4  
1 5

Sample Output:

0

Explanation:

In the first case you have to mark at least 3 vertices, and in the second case you don't need to mark any vertices.

Author

HackerRank

Difficulty

Hard

Max Score

70

Submitted By

1069

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature