Maximum Distinct Nodes in Chess Walk on Tree

Little Q is designing a chess‐like board game. In his game, the chess pieces are placed on grid points of a board. Some pairs of grid points are connected by edges, and a chess piece can move only between directly connected grid points. The board has \(V\) grid points, numbered from \(0,1,2,\dots,V-1\). The board is connected, meaning that a chess piece can reach any grid point starting from any grid point. Moreover, Little Q has designed the board so that the path between any two grid points is unique, which implies that the board’s structure forms a tree.

Starting at grid point \(0\), a chess piece makes exactly \(N\) moves. During the walk, grid points may be visited multiple times, but each grid point is only counted once. Little Q wonders: What is the maximum number of distinct grid points that the chess piece can visit in \(N\) moves?

Note: The input describes a tree with \(V\) nodes. The optimal strategy is to plan a walk that first reaches a farthest node from \(0\) (with distance \(d_{max}\)) and then, if extra moves remain, use them to branch out to visit additional new nodes. An important observation is that the minimum number of moves required to cover a set of \(K\) nodes in a tree (with \(0\) included) is \(2(K-1)-L\), where \(L\) is the maximum distance from \(0\) in that subtree. Using such reasoning, one can show that an optimal answer is given by:

[ answer = \begin{cases} N+1, & \text{if } N < d_{max}, \ \min\Bigl(V,; d_{max}+1+\left\lfloor\frac{N-d_{max}}{2}\right\rfloor\Bigr), & \text{if } N \ge d_{max}. \end{cases} ]

You are given \(V\) and \(N\) followed by \(V-1\) lines each containing two integers \(u\) and \(v\) that represent an edge between grid points \(u\) and \(v\). Output the maximum number of distinct grid points that can be visited in exactly \(N\) moves.

inputFormat

The first line contains two integers \(V\) and \(N\), where \(V\) is the number of grid points and \(N\) is the number of moves. The following \(V-1\) lines each contain two integers \(u\) and \(v\) indicating that there is an edge between grid points \(u\) and \(v\). It is guaranteed that the grid points form a tree with vertex 0 included.

outputFormat

Output a single integer, the maximum number of distinct grid points that can be visited in exactly \(N\) moves starting from grid point 0.

sample

4 3
0 1
1 2
1 3

3