P1272 Rebuilding Roads

After a terrible earthquake, people rebuilt Farmer John's ranch with $N$ barns (numbered $1 \sim N$). Since there was no time to build extra roads, there is a unique path between any two barns. Therefore, the ranch road network forms a tree. John wants to know how severe the damage would be in another earthquake. Some roads, once destroyed, would separate a subtree containing $P$ barns from the remaining barns. John wants to know the minimum number of such roads.

The first line contains two integers, $N$ and $P$. From the second line to the $N$-th line (i.e., $N - 1$ lines), each line contains two integers $I$ and $J$, indicating that node $I$ is the parent of node $J$. The road network can be built as a tree rooted at node $1$.

Output a single line containing the minimum number of roads whose destruction would separate a subtree with exactly $P$ nodes.

Sample explanation: If roads $1-4$ and $1-5$ are destroyed, the subtree containing nodes ($1, 2, 3, 6, 7, 8$) will be separated. Constraints: $1 \le N \le 150$, $1 \le P \le N$. It is guaranteed that the input forms a tree. Translated by ChatGPT 5