← 返回题目列表

AtCoder · arc179_d

D. 便携式门

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

你有一棵树 N 顶点编号 1, 2, \dots, N。的 i第一条边连接顶点 u_i 和 v_i 双向。

最初,所有顶点都被漆成白色。

为了有效地访问这棵树的所有顶点,爱丽丝发明了一个神奇的门。她使用一件一门按照以下程序进行旅行。

首先,她选择一个顶点并将棋子和门都放置在该顶点上。然后,她重复执行以下操作,直到所有顶点都被涂成黑色。

  • 选择以下操作之一:
    1. 将放置棋子的顶点涂成黑色。
    2. 选择与放置棋子的顶点相邻的顶点,并将棋子移动到该顶点。此操作的成本为 1.
    3. 将棋子移动到放置门的顶点。
    4. 将门移动到放置棋子的顶点。

请注意,只有第二个操作会产生成本。

可以证明,在有限次数的操作中可以将所有顶点涂成黑色。找出所需的最小总成本。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • 给定的图是一棵树。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
u_1 v_1
\vdots
u_{N-1} v_{N-1}

输出

打印答案。


示例输入 1

4
1 2
1 3
1 4

示例输出 1

3

这是 Alice 的过程的示例。让 (u, v) 表示棋子处于顶点的状态 u 并且门位于顶点 v.

  • 将棋子和门放置在顶点 4.
    • 现在的状态是 (4, 4).
  • 执行操作 1.
    • 顶点 4 被漆成黑色。
    • 现在的状态是 (4, 4).
  • 执行操作 2 并将棋子移动到顶点 1.
    • 这个费用 1.
    • 现在的状态是 (1, 4).
  • 执行操作 1.
    • 顶点 1 被漆成黑色。
  • 执行操作 4.
    • 现在的状态是 (1, 1).
  • 执行操作 2 并将棋子移动到顶点 2.
    • 这个费用 1.
    • 现在的状态是 (2, 1).
  • 执行操作 1.
    • 顶点 2 被漆成黑色。
  • 执行操作 3.
    • 现在的状态是 (1, 1).
  • 执行操作 2 并将棋子移动到顶点 3.
    • 这个费用 1.
    • 现在的状态是 (3, 1).
  • 执行操作 1.
    • 顶点 3 被漆成黑色。
    • 所有顶点现在都漆成黑色,因此过程结束。

执行操作的总成本 2 is 3,并且没有成本更小的程序。


示例输入 2

10
1 7
7 10
10 8
8 3
8 4
10 9
9 6
9 5
7 2

示例输出 2

10