{"problem":{"name":"「KDOI-02」一个网的路","description":{"content":" 敌对文明被惹怒了。他们想用一种奇怪的方式摧毁地球的路网。地球的路网可以近似为一个含有 $n$ 个节点 $m$ 条无向边的**森林**。他们想用以下 $2$ 种操作：   - 炸毁一个城市 $u$ 向外连接的所有道路。 - 在城市 $u,v$ 间新建一条道路。   来将地球上的路网改成效率最低的形式：一条链。现在你想知道，他们要达成目标最少需要操作几次。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8595"},"statements":[{"statement_type":"Markdown","content":"敌对文明被惹怒了。他们想用一种奇怪的方式摧毁地球的路网。地球的路网可以近似为一个含有 $n$ 个节点 $m$ 条无向边的**森林**。他们想用以下 $2$ 种操作：  \n\n- 炸毁一个城市 $u$ 向外连接的所有道路。\n- 在城市 $u,v$ 间新建一条道路。  \n\n来将地球上的路网改成效率最低的形式：一条链。现在你想知道，他们要达成目标最少需要操作几次。\n\n## Input\n\n从标准输入中读入数据。\n\n输入的第一行包含 $2$ 个正整数 $n,m$。\n\n接下来 $m$ 行，每行 $2$ 个正整数 $u,v$ ，表示在城市 $u,v$ 间有一条无向道路。\n\n## Output\n\n输出到标准输出。\n\n输出共一行一个整数，表示外星人的最少操作次数。\n\n[samples]\n\n## Background\n\n「{$&%#$~!@ovo}（他们也有路网？有趣。）」  \n「{&%#@~akoio!@}（该干的活先干完吧，玩物丧志的东西待会再说。）」  \n「{!%_&#%@yw?}（您语文是不是没学好？）」  \n蔚蓝的天空下，人们还不知道危险的来临。\n\n## Note\n\n**【样例解释】**\n\n+ **样例 1 解释：**  \n初始图：  \n![](https://cdn.luogu.com.cn/upload/image_hosting/2z6ava49.png)  \n对城市 $2,3$ 进行操作二。  \n![](https://cdn.luogu.com.cn/upload/image_hosting/lqhomfm5.png)  \n此时已经成为了一条链。\n\n***\n\n**【数据范围】**\n\n对于 $100\\%$ 的数据，$0\\le m<n\\le2\\times10^6$ 且保证输入合法。\n\n|测试点编号|$n\\le$|特殊性质|\n|:-:|:-:|:-:|\n|$1\\sim2$|$10$|A|\n|$3\\sim6$|$500$|无|\n|$7\\sim8$|$10^4$|A|\n|$9$|$10^4$|B|\n|$10\\sim12$|$10^4$|无|\n|$13\\sim15$|$10^6$|无|\n|$16\\sim20$|$2\\times10^6$|无|\n\n+ 特殊性质 A：保证每个连通块都为二叉树。\n+ 特殊性质 B：保证每个顶点的度数不超过 $2$。\n\n**【提示】**\n\n本题 I/O 量较大，推荐使用较快的 I/O 方式。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8595","tags":["动态规划 DP","贪心","2022","洛谷原创","O2优化","树形 DP"],"sample_group":[["3 1\n1 2","1"],["见附件中的 traffic2.in","见附件中的 traffic2.ans"],["见附件中的 traffic3.in","见附件中的 traffic3.ans"]],"created_at":"2026-03-03 11:09:25"}}