「KDOI-02」一个网的路

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