题目描述

给定一棵包含 $N$ 个顶点的树，顶点编号为 $1,2,\dots,N$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，为双向边。

所有顶点初始均被涂成白色。

为了高效地访问这棵树的所有顶点，Alice 发明了一个神奇的“门”。Alice 使用一个棋子和一个门，按照以下步骤进行旅行：

首先，任选一个顶点，将棋子和门都放在该顶点上。之后，重复以下操作，直到所有顶点都被涂成黑色为止：

• 从以下操作中任选一个执行：
  1. 将棋子所在的顶点涂成黑色。
  2. 选择一个与棋子当前所在顶点相邻的顶点，将棋子移动到该顶点，花费 $1$ 的代价。
  3. 将棋子移动到门所在的顶点。
  4. 将门移动到棋子所在的顶点。

注意，只有第 $2$ 种操作会产生代价。

可以证明，经过有限次操作后，所有顶点都能被涂成黑色。请你求出使总代价最小的方案的总代价。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

输出最小总代价。

样例 1

输入

4
1 2
1 3
1 4

输出

3

样例 2

输入

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

输出

10

说明/提示

限制条件

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

样例解释 1

以下是 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$ 共执行了 $3$ 次，因此总代价为 $3$。不存在比 $3$ 更小的总代价的方案。

由 ChatGPT 4.1 翻译