P3698 [CQOI2017] Xiao Q's Chessboard

Xiao Q is designing a board game. In the game he designed, pieces can be placed on the grid points on the board. Some pairs of grid points are connected by lines, and a piece may move only between grid points that are connected by a line. There are $V$ grid points in total, labeled $0, 1, 2, \cdots, V - 1$, and they are connected; that is, starting from any grid point, the piece can reach all grid points. Xiao Q also guarantees that the path between any two grid points is unique. Xiao Q now wants to know: starting from grid point $0$, after moving $N$ steps, what is the maximum number of grid points that can be visited? A grid point may be visited multiple times, but is counted only once.

The first line contains $2$ positive integers $V, N$, where $V$ is the total number of grid points and $N$ is the number of moves. Each of the next $V - 1$ lines contains two integers $a_i, b_i$, indicating that there is a line connecting grid points $a_i$ and $b_i$.

Output a single integer, the maximum number of grid points that can be visited.

[Explanation for Sample 1] From grid point $0$, move $2$ steps. The piece visits $0, 1, 2$, i.e., $3$ grid points. [Explanation for Sample 2] One feasible path is $0 \to 1 \to 3 \to 5 \to 3 \to 7$, visiting $0, 1, 3, 5, 7$, i.e., $5$ grid points. Constraints For $100\%$ of the testdata, $1 \le N, V \le 100$, and $0 \le a_i, b_i < V$. Translated by ChatGPT 5