CF1336A Linova and Kingdom

写轻小说是 Linova 生活中最重要的事情。昨晚，Linova 梦见了一个奇幻的王国。她一醒来就开始为这个王国写轻小说，当然，她是这个王国的女王。  王国中有 $n$ 个城市，以及 $n-1$ 条双向道路连接着这些城市中的若干对。你可以从任意一个城市出发，经过一些道路到达任意其他城市。城市编号为 $1$ 到 $n$，其中 $1$ 号城市是王都。因此，这个王国的结构是一棵树。 作为女王，Linova 计划选择恰好 $k$ 个城市发展工业，其余城市发展旅游业。王都也可以被选为工业城市或旅游城市。 每年都会在王都召开一次会议。每个工业城市都会派一名使者前往参会。所有使者都会沿着从出发城市到王都的唯一最短路径前进。 在旅游城市中旅行是愉快的。对于每位使者来说，他的幸福值等于他路径上经过的旅游城市的数量。 为了成为受人民爱戴的女王，Linova 想要选择 $k$ 个城市，使得所有使者的幸福值之和最大。你能帮她计算这个最大幸福值之和吗？

第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 2 \cdot 10^5$，$1 \le k < n$），分别表示城市数量和工业城市数量。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示城市 $u$ 和城市 $v$ 之间有一条道路相连。 保证任意两个城市之间都可以通过道路互达。

输出一行一个整数，表示所有使者的最大可能幸福值之和。

 在第一个样例中，Linova 可以选择城市 $2$、$5$、$6$、$7$ 发展工业，则来自城市 $2$ 的使者幸福值为 $1$，来自城市 $5$、$6$、$7$ 的使者幸福值为 $2$。幸福值之和为 $7$，且可以证明这是最大值。  在第二个样例中，选择城市 $3$、$4$ 发展工业可以得到幸福值之和为 $3$，但要注意 Linova 计划恰好选择 $k$ 个城市发展工业，因此最大幸福值为 $2$。 由 ChatGPT 4.1 翻译