{"problem":{"name":"[THUPC 2024 初赛] 一棵树","description":{"content":"这里有一棵树，具体的，这是一张有 $n$ 个节点和 $n-1$ 条边组成的无向联通图。 每个节点初始颜色为白色，你需要恰好将其中 $k$ 个节点染成黑色，定义一条边的权值是，断开这条边之后，两个连通块的黑色节点个数之差，定义一棵树的权值为所有边的权值求和，你需要最小化整棵树的权值。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9962"},"statements":[{"statement_type":"Markdown","content":"这里有一棵树，具体的，这是一张有 $n$ 个节点和 $n-1$ 条边组成的无向联通图。\n\n每个节点初始颜色为白色，你需要恰好将其中 $k$ 个节点染成黑色，定义一条边的权值是，断开这条边之后，两个连通块的黑色节点个数之差，定义一棵树的权值为所有边的权值求和，你需要最小化整棵树的权值。\n\n## Input\n\n第一行两个正整数 $n,k$（$1\\leq k\\leq n\\leq 5\\times10^5$）。\n\n接下来 $n-1$ 行，每行两个正整数 $x,y$ 表示树上的一条边。\n\n## Output\n\n输出共 $1$ 行，表示最优的染色方案下，这棵树的权值的最小值。\n\n[samples]\n\n## Note\n\n### 样例 \\#1 解释\n\n下图展示了一种满足条件的染色方案，边上的数字表示边权。\n\n![fig:sample](https://cdn.luogu.com.cn/upload/image_hosting/9i3ztp9r.png)\n\n### 题目使用协议\n\n来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。\n\n以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）\n\n1. 任何单位或个人都可以免费使用或转载本仓库的题目；\n\n2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；\n\n3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9962","tags":["平衡树","2024","凸包","THUPC","斜率维护技巧 slope trick","闵可夫斯基和 Minkowski sum"],"sample_group":[["10 4\n1 2\n2 3\n2 4\n3 5\n3 6\n3 7\n4 10\n6 8\n8 9\n","16\n"]],"created_at":"2026-03-03 11:09:25"}}