[CERC2019] Bob in Wonderland

Luogu
IDLGP9608
Time1000ms
Memory128MB
DifficultyP2
模拟2019ICPCCERC
众所周知,链条是由相连的环组成的。通常,所有环都具有相同的形状和大小。Bob 是一名铁匠学徒,他正在制作自己的第一条铱链。他遵循传统的链条制作通则。上面写着: - 如果没有链条,制作一个环,它将成为你链条的一部分。 - 如果有一条链,制作一个环,并将其连接到你已有的链中的另一个环上。 Bob 做了第一个环。然后,每次他制作另一个环时,他都会将其连接到链条上的其他环上,就像通则告诉他的那样。 当他完成时,他意识到他创造的物体根本不像一条普通的链。为了把链条拉直,他反复地拎起可能是链条两端的两个链环,并试图把它们尽可能地拉开。但在不同的地方,还有更多的“链条”从拉直的部分垂下来。 很明显,Bob 的工作还没有完成,他决定把他制作的物体称为未完成的链条。经过更多的思考,Bob 得出了一个结论,他必须更谨慎地断开一些环,并将它们重新连接到未完成的链条的其余部分,以获得他想要制作的直链。在直链中,每个环最多连接两个其他环,并且直链不能在不断开链环的情况下分离成更多的部分。 Bob 现在更加小心了,将用简单的步骤取得进展。在一个步骤中,他将在未完成的链条上,选择一个与环 B 相连接的另一个环 A 。然后,他会将 A 与 B 分开,并将 A 重新连接到未完成的链条中的另一个环 C。除环 B 外,Bob 将在整个步骤中保持其余原先与环 A 相连的环依旧与环 A 相连。 Bob 获得直链所需执行的最小步骤数是多少? ## Input 第一行包含一个整数 $N\ (1\le N\le 3\times 10^5)$,代表未完成的链条中的环数。所有环标号为 $1, 2, \dots, N$。 接下来 $N-1$ 行,每行包含两个整数,代表未完成链条中两个相连环的编号,按任意顺序给出。未完成的链条保证只有一个连体(即任意两个环之间都存在路径使他们相连)。 ## Output 输出一个整数,代表将 Bob 未完成的链条转化为直链的最少步骤数。 [samples] ## Background **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Bob in Wonderland](https://contest.felk.cvut.cz/19cerc/solved/bob.pdf)」** ## Note ### 样例解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/541l6nqd.png)
Samples
Input #1
5
4 3
1 2
4 5
3 2
Output #1
0
Input #2
6
1 3
3 2
3 4
4 5
4 6
Output #2
2
Input #3
7
1 2
2 3
3 4
4 5
3 6
6 7
Output #3
1
API Response (JSON)
{
  "problem": {
    "name": "[CERC2019] Bob in Wonderland",
    "description": {
      "content": "众所周知,链条是由相连的环组成的。通常,所有环都具有相同的形状和大小。Bob 是一名铁匠学徒,他正在制作自己的第一条铱链。他遵循传统的链条制作通则。上面写着: - 如果没有链条,制作一个环,它将成为你链条的一部分。 - 如果有一条链,制作一个环,并将其连接到你已有的链中的另一个环上。 Bob 做了第一个环。然后,每次他制作另一个环时,他都会将其连接到链条上的其他环上,就像通则告诉他的那样。 当",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9608"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "众所周知,链条是由相连的环组成的。通常,所有环都具有相同的形状和大小。Bob 是一名铁匠学徒,他正在制作自己的第一条铱链。他遵循传统的链条制作通则。上面写着:\n- 如果没有链条,制作一个环,它将成为你链条的一部分。\n- 如果有一条链,制作一个环,并将其连接到你已有的链中的另一个环上。\n\nBob 做了第一个环。然后,每次他制作另一个环时,他都会将其连接到链条上的其他环上,就像通则告诉他的那样。\n\n当...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments