Minimum Team Deployment on a Tree

In this problem, you are given a tree with n nodes and n - 1 edges. Every edge has length 1. The nodes are numbered from 1 to n. Each node (an outpost) can host a team, and a team stationed at a node can control all nodes that are within a distance of k (inclusive) from it.

Your task is to determine the minimum number of teams needed such that every node in the tree is controlled (i.e. every node is at distance at most k from at least one node where a team is stationed). It is guaranteed that the tree is connected (i.e. any two nodes can be reached by a unique path through the tree).

Note: The map (tree) comes with a detailed set of notes which hint that there is an optimal placement strategy. Use an efficient algorithm to decide on the minimum number of teams required.

The relation for the problem can be formulated in LaTeX as follows:

\(\text{Find } S \subseteq \{1, 2, \dots, n\} \text{ with minimum size such that } \forall u \in \{1,2,\dots,n\}, \exists v \in S \text{ with } d(u,v) \le k.\)

inputFormat

The first line contains two integers n and k (1 ≤ n ≤ 10⁵ (for example) and 0 ≤ k ≤ n), representing the number of nodes and the control radius of each team, respectively.

Each of the following n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n) which indicate that there is an edge between node u and node v with length 1.

outputFormat

Output a single integer, which is the minimum number of teams needed to control all nodes in the tree.

sample

6 1
1 2
1 3
2 4
2 5
3 6

2