Maximum Marked Nodes on a Tree with Distance Constraint

A cat is playing on a tree with n nodes. It wants to mark some nodes to claim its territory. However, any two marked nodes must be at least a distance d apart. Here the distance between two nodes is defined as the number of nodes on the unique simple path between them (including both endpoints); in other words, if two nodes are adjacent then the distance between them is 2.

Your task is to determine the maximum number of nodes the cat can mark while respecting the distance constraint. In particular, the cat may mark a node if and only if the distance from that node to any other already marked node is at least d (i.e. distance \(\ge d\)).

Note: When d = 1 or d = 2, any two distinct nodes satisfy the condition automatically (since the minimum distance between two distinct nodes is always 1+1=2), so the answer is simply n.

The input tree is given as an undirected connected tree with n nodes numbered 1 through n. You are free to choose any node as the root and solve the problem using tree dynamic programming.

The optimal solution uses a DFS based DP. Define a function \(f(u, state)\) that returns the maximum number of marked nodes in the subtree rooted at node \(u\) when the distance from \(u\) to the nearest marked node in the ancestors is state. Here we use an integer state with the following meaning:

• If state = d we consider it as "free" (i.e. there is no conflict from above), and we have the option to mark node \(u\) or not.
• If state < d then node \(u\) cannot be marked because it is too close to some marked ancestor. In that case the state for its children will be \(min(state+1, d)\).

When \(state = d\), we have two choices at node \(u\):

1. Mark \(u\): This is allowed only when \(state = d\). Then the contribution is 1 (for \(u\)) plus, for every child \(v\), we call \(f(v, 2)\) since the distance from \(v\) to \(u\) (which is marked) is 2.
2. Do not mark \(u\): Then for every child \(v\) the new state remains \(d\) (if \(state=d\)) or becomes \(min(state+1,d)\) if \(state<d\).

The answer is \(f(root, d)\) where we start with the free state at the root (choose node 1 as the root). The DP recurrences ensure that the distance condition is always satisfied.

inputFormat

The first line contains two integers n and d (1 ≤ n ≤ 10⁵, 1 ≤ d ≤ n+1), where n is the number of nodes in the tree and d is the distance constraint.

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

outputFormat

Output a single integer, the maximum number of nodes that can be marked under the given constraint.

sample

1 3

1