← 返回题目列表

Codeforces · 1336/A

A. 利诺瓦和王国

中文机器翻译题面 查看原题

写轻小说是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$$$。

保证从任何城市,您都可以通过公路到达任何其他城市。

输出

打印唯一包含单个整数的行 - 所有特使的最大可能幸福总和。

示例

输入 #1

7 4
1 2
1 3
1 4
3 5
3 6
4 7

输出 #1

7

输入 #2

4 1
1 2
1 3
2 4

输出 #2

2

输入 #3

8 5
7 5
1 7
6 1
3 7
8 3
2 1
4 5

输出 #3

9

注意

第一个例子中,Linova可以选择城市$$$2$$$、$$$5$$$、$$$6$$$、$$$7$$$发展工业,那么来自城市$$$2$$$的使者幸福感为$$$1$$$,来自城市$$$5$$$、$$$6$$$、$$$7$$$的幸福感为$$$5$$$、$$$6$$$、$$$7$$$ $$$2$$$。幸福的总和是$$$7$$$,并且可以证明是最大的。

在第二个例子中,选择城市$$$3$$$、$$$4$$$发展工业可以达到$$$3$$$的总和,但请记住Linova计划恰好选择$$$k$$$城市发展工业,那么最大总和是$$$2$$$。