P9962 [THUPC 2024 Preliminary] A Tree

Here is a tree. Specifically, it is an undirected connected graph with $n$ nodes and $n-1$ edges. Each node is initially colored white. You need to color exactly $k$ of the nodes black. Define the weight of an edge as follows: after cutting this edge, take the difference between the numbers of black nodes in the two connected components. Define the weight of the whole tree as the sum of the weights of all edges. You need to minimize the weight of the entire tree.

The first line contains two positive integers $n, k$ ($1\leq k\leq n\leq 5\times10^5$). The next $n-1$ lines each contain two positive integers $x, y$, representing an edge in the tree.

Output 1 line, representing the minimum possible weight of the tree under an optimal coloring scheme.

### Sample \#1 Explanation The figure below shows a coloring scheme that satisfies the requirements. The numbers on the edges indicate edge weights.  ### Problem Usage Agreement From the THUPC2024 (2024 Tsinghua University Student Programming Contest and Collegiate Invitational Contest) Preliminary. The following “this repository” refers to the THUPC2024 Preliminary official repository ([https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)). 1. Any organization or individual may use or repost the problems in this repository for free. 2. When using the problems in this repository, any organization or individual should keep it free and public. It is strictly forbidden to profit from these problems or to add special permissions to them. 3. If possible, when using the problems in this repository, please also provide how to obtain resources such as testdata, standard solutions, and explanations. Otherwise, please attach the GitHub link of this repository. Translated by ChatGPT 5