A5684. 「THUPC 2024 初赛」一棵树
编程题
NOI/NOI+/CTSC
知识点
题目描述
这里有一棵树，具体的，这是一张有 $n$ 个节点和 $n-1$ 条边组成的无向联通图。
每个节点初始颜色为白色，你需要恰好将其中 $k$ 个节点染成黑色，定义一条边的权值是，断开这条边之后，两个连通块的黑色节点个数之差，定义一棵树的权值为所有边的权值求和，你需要最小化整棵树的权值。
每个节点初始颜色为白色，你需要恰好将其中 $k$ 个节点染成黑色，定义一条边的权值是，断开这条边之后，两个连通块的黑色节点个数之差，定义一棵树的权值为所有边的权值求和，你需要最小化整棵树的权值。
输入格式
第一行两个正整数 $n,k$（$1\leq k\leq n\leq 5\times10^5$）。
接下来 $n-1$ 行，每行两个正整数 $x,y$ 表示树上的一条边。
接下来 $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