AT_arc179_d [ARC179D] Portable Gate

给定一棵包含 $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}$

输出最小总代价。

### 限制条件 - $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 翻译