分数: 700 点
问题陈述
你有一棵树 N 顶点编号 1, 2, \dots, N。的 i第一条边连接顶点 u_i 和 v_i 双向。
最初,所有顶点都被漆成白色。
为了有效地访问这棵树的所有顶点,爱丽丝发明了一个神奇的门。她使用一件一门按照以下程序进行旅行。
首先,她选择一个顶点并将棋子和门都放置在该顶点上。然后,她重复执行以下操作,直到所有顶点都被涂成黑色。
- 选择以下操作之一:
- 将放置棋子的顶点涂成黑色。
- 选择与放置棋子的顶点相邻的顶点,并将棋子移动到该顶点。此操作的成本为 1.
- 将棋子移动到放置门的顶点。
- 将门移动到放置棋子的顶点。
请注意,只有第二个操作会产生成本。
可以证明,在有限次数的操作中可以将所有顶点涂成黑色。找出所需的最小总成本。
约束
- 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