CF1375G.Tree Modification

You are given a tree with $n$ vertices. You are allowed to modify the structure of the tree through the following multi-step operation:

1. Choose three vertices $a$, $b$, and $c$ such that $b$ is adjacent to both $a$ and $c$.
2. For every vertex $d$ other than $b$ that is adjacent to $a$, remove the edge connecting $d$ and $a$ and add the edge connecting $d$ and $c$.
3. Delete the edge connecting $a$ and $b$ and add the edge connecting $a$ and $c$.

As an example, consider the following tree:

The following diagram illustrates the sequence of steps that happen when we apply an operation to vertices $2$, $4$, and $5$:

It can be proven that after each operation, the resulting graph is still a tree.

Find the minimum number of operations that must be performed to transform the tree into a star. A star is a tree with one vertex of degree $n - 1$, called its center, and $n - 1$ vertices of degree $1$.

给你一棵包含 $n$ 个顶点的树。你可以通过以下多步操作来修改该树的结构：

1. 选择三个顶点 $a$、$b$ 和 $c$，使得 $b$ 同时与 $a$ 和 $c$ 相邻。
2. 对于每一个除 $b$ 外与 $a$ 相邻的顶点 $d$，删除边 $(d, a)$，并添加边 $(d, c)$。
3. 删除边 $(a, b)$，并添加边 $(a, c)$。

例如，考虑如下这棵树：

下图展示了对顶点 $2$、$4$、$5$ 执行一次操作时所发生的步骤序列：

可以证明：每次操作后所得图仍为一棵树。

求将该树变为星形图所需的最少操作次数。星形图是一种树，其中存在一个度数为 $n - 1$ 的顶点（称为中心），其余 $n - 1$ 个顶点的度数均为 $1$。

The first line contains an integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

The $i$-th of the following $n - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$) denoting that there exists an edge connecting vertices $u_i$ and $v_i$. It is guaranteed that the given edges form a tree.

第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）——树中顶点的数量。

接下来的 $n - 1$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示顶点 $u_i$ 与 $v_i$ 之间存在一条边。保证所给的边构成一棵树。

Print a single integer — the minimum number of operations needed to transform the tree into a star.

It can be proven that under the given constraints, it is always possible to transform the tree into a star using at most $10^{18}$ operations.

输出一个整数——将树转化为星形图所需的最少操作次数。

在给定约束条件下，可以证明总能通过至多 $10^{18}$ 次操作将树转化为星形图。

The first test case corresponds to the tree shown in the statement. As we have seen before, we can transform the tree into a star with center at vertex $5$ by applying a single operation to vertices $2$, $4$, and $5$.

In the second test case, the given tree is already a star with the center at vertex $4$, so no operations have to be performed.

第一个测试用例对应题目描述中所示的树。如前所述，我们可以通过对顶点 $2$、$4$ 和 $5$ 执行一次操作，将该树转化为以顶点 $5$ 为中心的星形树。

第二个测试用例中，给定的树本身已是中心为顶点 $4$ 的星形树，因此无需执行任何操作。