题目描述
这里有一棵树,具体的,这是一张有 n 个节点和 n−1 条边组成的无向联通图。
每个节点初始颜色为白色,你需要恰好将其中 k 个节点染成黑色,定义一条边的权值是,断开这条边之后,两个连通块的黑色节点个数之差,定义一棵树的权值为所有边的权值求和,你需要最小化整棵树的权值。
输入格式
第一行两个正整数 n,k(1≤k≤n≤5×105)。
接下来 n−1 行,每行两个正整数 x,y 表示树上的一条边。
输出格式
输出共 1 行,表示最优的染色方案下,这棵树的权值的最小值。
样例1输入
10 4
1 2
2 3
2 4
3 5
3 6
3 7
4 10
6 8
8 9
样例1输出
16
样例1解释
下图展示了一种满足条件的染色方案,边上的数字表示边权。