CF1375G Tree Modification

给定一棵有 $n$ 个顶点的树。你可以通过以下多步操作修改树的结构： 1. 选择三个顶点 $a$、$b$、$c$，其中 $b$ 同时与 $a$ 和 $c$ 相邻。 2. 对于所有与 $a$ 相邻且不为 $b$ 的顶点 $d$，删除 $d$ 与 $a$ 之间的边，并添加 $d$ 与 $c$ 之间的边。 3. 删除 $a$ 与 $b$ 之间的边，并添加 $a$ 与 $c$ 之间的边。 例如，考虑下图中的树：  下图展示了对顶点 $2$、$4$、$5$ 应用一次操作后发生的变化：  可以证明，每次操作后，得到的图仍然是一棵树。 请你求出将这棵树变为一棵星形树所需的最少操作次数。星形树是指有一个度数为 $n-1$ 的顶点（称为中心），其余 $n-1$ 个顶点的度数均为 $1$ 的树。

第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$），表示树的顶点数。 接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示存在一条连接顶点 $u_i$ 和 $v_i$ 的边。保证给定的边构成一棵树。

输出一个整数，表示将树变为星形树所需的最少操作次数。 可以证明，在给定的约束下，总能在不超过 $10^{18}$ 次操作内将树变为星形树。

第一个测试用例对应题目描述中的树。如前所述，我们可以通过对顶点 $2$、$4$、$5$ 应用一次操作，将树变为以顶点 $5$ 为中心的星形树。 第二个测试用例中，给定的树已经是以顶点 $4$ 为中心的星形树，因此不需要进行任何操作。 由 ChatGPT 4.1 翻译